Shelf Packing Problem

Packing

Problem

In the Shelf Packing Problem, a number of items with known weights and known categories must be assigned to bins with uniform capacity placed on shelves. The total weight on a shelf, in addition to the number of items belonging to a given category placed on a shelf, are limited.The objective is to minimize the number of shelves (first objective function) and then the number of bins (second objective function) used to place all items. This problem is a variation of the Bin Packing Problem (BPP) and is then NP-hard.

Principles learned

Data

The Shelf Packing Problem instances are randomly generated JSON files. They are composed of the following elements:

  • “nbItems”
  • “nbShelves”
  • “nbCategories”
  • “binCapacity”
  • “shelfCapacity”
  • “itemWeights”
  • “itemCategories”
  • “limitCategories” : limitCategories[c] is the maximum number of items of category c on a shelf
  • “binsAssignment” : binsAssignment[s] is the list of the bins assigned to the shelf s

We use JSON libraries for each API model to read the instance data and write the output solution: C# (Newtonsoft.Json), Java (gson-2.8.8), python (json), C++ (nlohmann/json.hpp). For Hexaly Modeler, the JSON module is used.

Program

The model implemented here makes use of set variables.

Each shelf has several bins on it and for each shelf, we define a intermediate expression as the ‘union‘ of the items in the bins assigned to that specific shelf.

For every bin, we define a set which describes the items assigned to that bin. Those sets are constrained to form a ‘partition‘, which means that an item must be assigned to exactly one bin.
The sum of the weights of the items assigned to a bin must not exceed the bin capacity.
The sum of the weights of the items on a shelf must not exceed the shelf capacity.
On any shelf, the number of items of a given category must not exceed the limit imposed. To implement this constraint we perform the ‘intersection’ the items on a shelf and the items of a category and impose their count to remain below the limitCategories[c] threshold.

The objective is to first minimize the number of used shelves (first objective) and then the number of used bins (second objective).

Execution

hexaly shefpacking.hxm inFileName=instances/instance_0.json [solFileName=] [hxTimeLimit=]

use io;
use json;

// Read instance data 
function input() {
    local usage = "Usage: hexaly shelf_packing.hxm "
            + "inFileName=inputFile [solFileName=outputFile] [hxTimeLimit=timeLimit]";

    if (inFileName == nil) throw usage;
    data = json.parse(inFileName);

    nbItems = data.nbItems;
    nbShelves = data.nbShelves;
    nbCategories = data.nbCategories;
    nbMaxBins = nbItems;

    binCapacity = data.binCapacity;
    shelfCapacity = data.shelfCapacity;

    weights = data.itemWeights;
    categories = data.itemCategories;
    // limitCategories[c]: maximum number of items of category c on a shelf 
    limitCategories = data.limitCategories;

    // binAssignment[s]: list of bins assigned to shelf s 
    binsAssignment = data.binsAssignment;

}

// Declare the optimization model 
function model() {

    // Set decisions: bins[k] represents the items in bin k
    bins[k in 0...nbMaxBins] <- set(nbItems);

    // Compute the union of bins on the same shelf to get all the items on this shelf
    shelves[k in 0...nbShelves] <-union[i in binsAssignment[k]](bins[i]);

    // Constraint: Each item must be in one bin and one bin only 
    constraint partition[k in 0...nbMaxBins](bins[k]);
    
    for [k in 0...nbMaxBins] {
        binWeights[k] <- sum(bins[k], i => weights[i]);
        
        // Constraint: Weight constraint on each bin 
        constraint binWeights[k] <= binCapacity;
    
        // Bin k is used if at least one item is in it 
        binIsUsed[k] <- (count(bins[k]) > 0);
    }

    for [s in 0...nbShelves] {
        shelfWeights[s] <- sum(shelves[s], i => weights[i]);

        // Constraint: Weight constraint on each shelf 
        constraint shelfWeights[s] <= shelfCapacity;

        for [c in 0...nbCategories] {
            local itemsOfCategory <- array[i in 0...nbItems : categories[i]==c](i);
            // Constraint: the number of items per category on a shelf is limited 
            constraint count(intersection(shelves[s], itemsOfCategory)) <= limitCategories[c];
        }
        // Shelf s is used if at least one item is on it 
        shelfIsUsed[s] <- (count(shelves[s]) > 0);
    }

    totalShelvesUsed <- sum[s in 0...nbShelves](shelfIsUsed[s]);
    totalBinsUsed <- sum[k in 0...nbMaxBins](binIsUsed[k]);

    // Minimize the number of used shelves (first objective) then bins (second objective) 
    minimize totalShelvesUsed;
    minimize totalBinsUsed;
}

// Parametrize the solver 
function param() {
    if (hxTimeLimit == nil) hxTimeLimit = 5;  

}

// Write the output file  
function output() {
    if (solFileName == nil) return;
    local solFile = io.openWrite(solFileName);
    for [s in 0...nbShelves]{
        if (shelves[s].value.count() == 0) continue;
        solFile.print("Shelf "+ s +" total weight: ", shelfWeights[s].value, "/", shelfCapacity);
        solFile.println();
        for [k in 0...nbMaxBins] {
            if (bins[k].value.count() == 0) continue;
            solFile.print(">Bin weight: ", binWeights[k].value, "/", binCapacity, " | Items: ");
            for [e in bins[k].value]
                solFile.print("#"+e + " ");
            solFile.println();
        }
    }
}
Execution (Windows)
set PYTHONPATH=%HX_HOME%\bin\python
python shelfpacking.py instances/instance_0.json
Execution (Linux)
export PYTHONPATH=/opt/hexaly_14_0/bin/python
python shelfpacking.py instances/instance_0.json
import hexaly.optimizer
import json
import sys
import math

if len(sys.argv) < 2:
    print("Usage: python shelf_packing.py inputFile [outputFile] [timeLimit]")
    sys.exit(1)

with hexaly.optimizer.HexalyOptimizer() as optimizer:
    # Read instance data
    filename = sys.argv[1]
    with open(filename, 'r') as file:
        data = json.load(file)
        nb_items = data["nbItems"]
        nb_categories = data["nbCategories"]
        nb_shelves = data["nbShelves"]
        bin_capacity = data["binCapacity"]
        shelf_capacity = data["shelfCapacity"]
        weights_data = data["itemWeights"]
        categories_data = data["itemCategories"]

        # limitCategories[c]: maximum number of items of category c on a shelf
        limit_categories = data["limitCategories"]
        # binAssignment[s]: list of bins assigned to shelf s               
        bins_assignment = data["binsAssignment"]

    nb_max_bins = nb_items

    #
    # Declare the optimization model
    #
    model = optimizer.model

    # Set decisions: bins[k] represents the items in bin k
    bins = [model.set(nb_items) for _ in range(nb_max_bins)]

    # Shelves are the sets of items contained in the union of bins belonging to said shelf
    shelves = [model.union(bins[b] for b in bins_assignment[s]) for s in range(nb_shelves)]

    # Constraint: Each item must be in one bin and one bin only
    model.constraint(model.partition(bins))

    # Create an array and a function to retrieve the item's weight
    weights = model.array(weights_data)
    categories = model.array(categories_data)
    weight_lambda = model.lambda_function(lambda i: weights[i])

    # Constraint: Weight constraint on each bin
    bin_weights = [model.sum(b, weight_lambda) for b in bins]
    for w in bin_weights:
        model.constraint(w <= bin_capacity)

    # Bin b is used if at least one item is in it
    bins_used = [model.count(b) > 0 for b in bins]

    # Constraint: Weight constraint on each shelf
    shelves_weights = [model.sum(s, weight_lambda) for s in shelves]
    for w in shelves_weights:
        model.constraint(w <= shelf_capacity)

    # Constraint: the number of items per category on a shelf is limited
    for c in range(nb_categories):
        items_per_category = []
        for i in range(nb_items):
            if categories_data[i] == c:
                items_per_category.append(i)
        items_per_category_array = model.array(items_per_category)
        for s in shelves:
            model.constraint(model.count(model.intersection(s, items_per_category_array)) <= limit_categories[c])

    # Shelf s is used if at least one item is on it
    shelves_used = [model.count(s) > 0 for s in shelves]

    total_shelves_used = model.sum(shelves_used)
    total_bins_used = model.sum(bins_used)

    # Minimize the number of used shelves (first objective) then bins (second objective)
    model.minimize(total_shelves_used)
    model.minimize(total_bins_used)
    model.close()

    # Parameterize the optimizer
    if len(sys.argv) >= 4:
        optimizer.param.time_limit = int(sys.argv[3])
    else:
        optimizer.param.time_limit = 5

    optimizer.solve()

    # Write the solution in a file
    if len(sys.argv) >= 3:
        with open(sys.argv[2], 'w') as f:
            for s in range(nb_shelves):
                if shelves_used[s].value:
                    f.write("Shelf %d total weight: %d/%d \n" %(s, shelves_weights[s].value, shelf_capacity) )
                    for k in range(nb_max_bins):
                        if bins_used[k].value:
                            f.write(">Bin weight: %d/%d | Items: " % (bin_weights[k].value, bin_capacity))
                            for e in bins[k].value:
                                f.write("#%d " % e)
                            f.write("\n")
Compilation / Execution (Windows)
cl /EHsc ShelfPacking.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly140.lib
ShelfPacking instances\/instance_0.json
Compilation / Execution (Linux)
g++ ShelfPacking.cpp -I/opt/hexaly_14_0/include -lhexaly140 -lpthread -o ShelfPacking
./ShelfPacking instances/instance_0.json
#include "optimizer/hexalyoptimizer.h"
#include <cmath>
#include <fstream>
#include <iostream>
#include <numeric>
#include <vector>
#include "json.hpp"
#include <map>
#include <sstream>
#include <vector>

using namespace hexaly;
using namespace std;
using json = nlohmann::json;

class BinShelfPacking {
public:
    // Number of items, shelves, categories and bins 
    int nbItems;
    int nbShelves;
    int nbCategories;
    int nbMaxBins;

    // Capacity of each bin, shelf 
    int binCapacity;
    int shelfCapacity;

    // Weight of each item 
    vector<int> weightsData;

    // Category of each item 
    vector<int> categoriesData;

    // limitCategories[c]: maximum number of items of category c on a shelf 
    vector<int> limitCategories;

    // binAssignment[s]: list of bins assigned to shelf s 
    vector<vector<int>> binsAssignment;

    // Hexaly Optimizer 
    HexalyOptimizer optimizer;

    // Decision variables 
    vector<HxExpression> bins;

    // Shelves (union of bins) 
    vector<HxExpression> shelves;

    // Weight of each bin, shelf in the solution 
    vector<HxExpression> binWeights;
    vector<HxExpression> shelfWeights;

    // Whether the bin, shelf is used in the solution 
    vector<HxExpression> binsUsed;
    vector<HxExpression> shelvesUsed;

    // Objectives 
    HxExpression totalBinsUsed;
    HxExpression totalShelvesUsed;

    // Read instance data 
    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        infile.open(fileName.c_str());

        json data;
        infile >> data;
        infile.close();

        nbItems = data["nbItems"];
        nbCategories = data["nbCategories"];
        nbShelves = data["nbShelves"];
        binCapacity = data["binCapacity"];
        shelfCapacity = data["shelfCapacity"];

        weightsData.resize(nbItems);
        categoriesData.resize(nbItems);
        limitCategories.resize(nbCategories);

        for (int i = 0; i < nbItems; ++i){
            weightsData[i] = data["itemWeights"][i];
            categoriesData[i] = data["itemCategories"][i];
        }
        for (int c = 0; c < nbCategories; ++c){
            limitCategories[c] = data["limitCategories"][c];
        }
        binsAssignment.resize(nbShelves);
        for (int s = 0; s < nbShelves; ++s){
            for (int b: data["binsAssignment"][s]) {
                binsAssignment[s].push_back(b);
            }
        }

        nbMaxBins = nbItems;
    }

    void solve(int limit) {
        // Declare the optimization model 
        HxModel model = optimizer.getModel();

        bins.resize(nbMaxBins);
        binWeights.resize(nbMaxBins);
        binsUsed.resize(nbMaxBins);
        shelves.resize(nbShelves);
        shelfWeights.resize(nbShelves);
        shelvesUsed.resize(nbShelves);

        HxExpression binsArray = model.array();

        // Set decisions: bins[k] represents the items in bin k 
        for (int k = 0; k < nbMaxBins; ++k) {
            bins[k] = model.setVar(nbItems);
        }

        // Compute the union of bins on the same shelf to get all the items on this shelf
        for (int s = 0; s < nbShelves; ++s) {
            HxExpression shelf = model.union_();
            for (int b : binsAssignment[s]) {
                shelf.addOperand(bins[b]);
            }
            shelves[s] = shelf;
        }

        // Constraint: Each item must be in one bin and one bin only 
        model.constraint(model.partition(bins.begin(), bins.end()));

        
        HxExpression weights = model.array(weightsData.begin(), weightsData.end());
        HxExpression weightLambda = model.createLambdaFunction([&](HxExpression i) { return weights[i]; });
        for (int k = 0; k < nbMaxBins; ++k) {
            // Constraint: Weight constraint on each bin 
            binWeights[k] = model.sum(bins[k], weightLambda);
            model.constraint(binWeights[k] <= binCapacity);

            // Bin k is used if at least one item is in it
            binsUsed[k] = model.count(bins[k]) > 0;
        }

        for (int s = 0; s < nbShelves; ++s) {
            // Constraint: the number of items per category on a shelf is limited
            shelfWeights[s] = model.sum(shelves[s], weightLambda);
            model.constraint(shelfWeights[s] <= shelfCapacity);

            // Shelf s is used if at least one item is on it 
            shelvesUsed[s] = model.count(shelves[s]) > 0;

            for (int c = 0; c < nbCategories; ++c) {
                HxExpression itemsPerCategory = model.array();
                for (int i = 0; i < nbItems; ++i) {
                    if (categoriesData[i] == c) {
                        itemsPerCategory.addOperands(i);
                    }
                }
                // Constraint: the number of items per category on a shelf is limited 
                HxExpression shelfIntersection= model.intersection(itemsPerCategory, shelves[s]);
                model.constraint(model.count(shelfIntersection) <= limitCategories[c]);
            }
        }

        totalShelvesUsed = model.sum(shelvesUsed.begin(), shelvesUsed.end());
        totalBinsUsed = model.sum(binsUsed.begin(), binsUsed.end());

        // Minimize the number of used shelves (first objective) then bins (second objective) 
        model.minimize(totalShelvesUsed);
        model.minimize(totalBinsUsed);

        model.close();

        // Parametrize the optimizer 
        optimizer.getParam().setTimeLimit(limit);

        optimizer.solve();
    }

    // Write the output file  
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());
        for (int s = 0; s < nbShelves; ++s){
            if (shelvesUsed[s].getValue()) {
                outfile << "Shelf " << s << " total weight: " << shelfWeights[s].getValue() << " / " << shelfCapacity;
                outfile << endl;
                for (int k = 0; k < nbMaxBins; ++k) {
                    if (binsUsed[k].getValue()) {
                        outfile << ">Bin weight: " << binWeights[k].getValue() << " / " << binCapacity << " | Items: ";
                        HxCollection binCollection = bins[k].getCollectionValue();
                        for (int i = 0; i < binCollection.count(); ++i) {
                            outfile << "#" << binCollection[i] << " ";
                        }
                        outfile << endl;
                    }
                }
            }
        }
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: shelf_packing inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }
    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "5";

    try {
        BinShelfPacking model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const exception& e) {
        cerr << "An error occurred: " << e.what() << endl;
        return 1;
    }
}
Compilation / Execution (Windows)
copy %HX_HOME%\bin\Hexaly.NET.dll .
csc ShelfPacking.cs /reference:Hexaly.NET.dll
ShelfPacking instances\instance_0.json
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using Hexaly.Optimizer;

using Newtonsoft.Json.Linq;
using Newtonsoft.Json;

public class BinShelfPacking : IDisposable
{

    // Number of items, shelves, categories and bins
    int nbItems;
    int nbShelves;
    int nbCategories;
    int nbMaxBins;

    // Capacity of each bin, shelf 
    int binCapacity;
    int shelfCapacity;

    // Weight of each item 
    long[] weightsData;
    
    // Category of each item 
    long[] categoriesData;

    // limitCategories[c]: maximum number of items of category c on a shelf 
    long[] limitCategories;

    // binAssignment[s]: list of bins assigned to shelf s 
    long[][] binsAssignment;

    // Hexaly Optimizer 
    HexalyOptimizer optimizer;

    // Decision variables 
    HxExpression[] bins;

    // Shelves (union of bins) 
    HxExpression[] shelves;

    // Weight of each bin, shelf in the solution 
    HxExpression[] binWeights;
    HxExpression[] shelfWeights;

    // Whether the bin, shelf is used in the solution 
    HxExpression[] binsUsed;
    HxExpression[] shelvesUsed;

    // Objectives 
    HxExpression totalBinsUsed;
    HxExpression totalShelvesUsed;

    public BinShelfPacking()
    {
        optimizer = new HexalyOptimizer();
    }

    // Read instance data 
    void ReadInstance(string fileName)
    {
        JObject data = JObject.Parse(File.ReadAllText(fileName));

        nbItems = data["nbItems"].Value<int>();
        nbCategories = data["nbCategories"].Value<int>();
        nbShelves = data["nbShelves"].Value<int>();
        binCapacity = data["binCapacity"].Value<int>();
        shelfCapacity = data["shelfCapacity"].Value<int>();

        weightsData = new long[nbItems];
        categoriesData = new long[nbItems];
        limitCategories = new long[nbCategories];
        binsAssignment = new long[nbShelves][];

        JArray weightsDataArray = (JArray)data["itemWeights"];
        JArray categoriesDataArray = (JArray)data["itemCategories"];
        for (int i = 0; i < nbItems; ++i)
        {
            weightsData[i] = weightsDataArray[i].Value<int>();
            categoriesData[i] = categoriesDataArray[i].Value<int>();
        }

        JArray limitCategoriesArray = (JArray)data["limitCategories"];
        for (int c = 0; c < nbCategories; ++c)
        {
            limitCategories[c] = limitCategoriesArray[c].Value<int>();
        }

        JArray binsAssignmentJsonArray = (JArray)data["binsAssignment"];
        int shelfIdx = 0;
        foreach (JArray shelfAssignement in binsAssignmentJsonArray)
        {
            binsAssignment[shelfIdx] = new long[shelfAssignement.Count];
            for (int binIdx = 0; binIdx < shelfAssignement.Count; ++binIdx)
            {
                binsAssignment[shelfIdx][binIdx] = (long)shelfAssignement[binIdx];
            }
            shelfIdx++;
        }

        nbMaxBins = nbItems;
    }

    public void Dispose()
    {
        if (optimizer != null)
            optimizer.Dispose();
    }

    void Solve(int limit)
    {
        // Declare the optimization model
        HxModel model = optimizer.GetModel();

        bins = new HxExpression[nbMaxBins];
        shelves = new HxExpression[nbShelves];
        binWeights = new HxExpression[nbMaxBins];
        shelfWeights = new HxExpression[nbShelves];
        binsUsed = new HxExpression[nbMaxBins];
        shelvesUsed = new HxExpression[nbShelves];
        
        // Set decisions: bins[k] represents the items in bin k 
        for (int k = 0; k < nbMaxBins; ++k)
        {
            bins[k] = model.Set(nbItems);
        }

        // Compute the union of bins on the same shelf to get all the items on this shelf
        for (int s = 0; s < nbShelves; ++s) {
            HxExpression shelf = model.Union();
            for (int i = 0; i < binsAssignment[s].Count(); ++i)
            {
                shelf.AddOperand(bins[binsAssignment[s][i]]);
            }
            shelves[s] = shelf;
        }

        // Constraint: Each item must be in one bin and one bin only 
        model.Constraint(model.Partition(bins));

        HxExpression weights = model.Array(weightsData);
        HxExpression weightLambda = model.LambdaFunction(i => weights[i]);
        for (int k = 0; k < nbMaxBins; ++k)
        {
            // Constraint: Weight constraint on each bin 
            binWeights[k] = model.Sum(bins[k], weightLambda);
            model.Constraint(binWeights[k] <= binCapacity);

            // Bin k is used if at least one item is in it
            binsUsed[k] = model.Count(bins[k]) > 0;
        }

        for (int s = 0; s < nbShelves; ++s)
        {
            // Constraint: the number of items per category on a shelf is limited
            shelfWeights[s] = model.Sum(shelves[s], weightLambda);
            model.Constraint(shelfWeights[s] <= shelfCapacity);

            // Shelf s is used if at least one item is on it 
            shelvesUsed[s] = model.Count(shelves[s]) > 0;

            for (int c = 0; c < nbCategories; ++c) {
                HxExpression itemsPerCategory = model.Array();
                for (int i = 0; i < nbItems; ++i) {
                    if (categoriesData[i] == c) {
                        itemsPerCategory.AddOperand(i);
                    }
                }
                // Constraint: the number of items per category on a shelf is limited 
                HxExpression shelfIntersection = model.Intersection(itemsPerCategory, shelves[s]);
                model.Constraint(model.Count(shelfIntersection) <= limitCategories[c]);
            }
        }

        totalShelvesUsed = model.Sum(shelvesUsed);
        totalBinsUsed = model.Sum(binsUsed);

        // Minimize the number of used shelves (first objective) then bins (second objective) 
        model.Minimize(totalShelvesUsed);
        model.Minimize(totalBinsUsed);

        model.Close();

        // Parametrize the optimizer 
        optimizer.GetParam().SetTimeLimit(limit);

        optimizer.Solve();
    }

    // Write the output file  
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            for (int s = 0; s < nbShelves; ++s)
            {
                if (shelvesUsed[s].GetValue() != 0)
                {
                    output.Write("Shelf "+ s +" total weight: " + shelfWeights[s].GetValue() + "/" + shelfCapacity);
                    output.WriteLine();
                    for (int k = 0; k < nbMaxBins; ++k)
                    {
                        if (binsUsed[k].GetValue() != 0)
                        {
                            output.Write(">Bin weight: " + binWeights[k].GetValue() + "/" + binCapacity + " | Items: ");
                            HxCollection binCollection = bins[k].GetCollectionValue();
                            for (int i = 0; i < binCollection.Count(); ++i)
                                output.Write("#" + binCollection[i] + " ");
                            output.WriteLine();
                        }
                    }
                }
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: ShelfPacking inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "5";

        using (BinShelfPacking model = new BinShelfPacking())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac ShelfPacking.java -cp %HX_HOME%\bin\hexaly.jar
java -cp %HX_HOME%\bin\hexaly.jar;. ShelfPacking instances\instance_0.json
Compilation / Execution (Linux)
javac BinPackingConflicts.java -cp /opt/hexaly_14_0/bin/hexaly.jar
java -cp /opt/hexaly_14_0/bin/hexaly.jar: .ShelfPacking instances\instance_0.json
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

import com.google.gson.*;
import com.google.gson.stream.*;

public class ShelfPacking {
    // Number of items, shelves, categories and bins
    private int nbItems;
    private int nbShelves;
    private int nbCategories;
    private int nbMaxBins;

    // Capacity of each bin, shelf 
    private int binCapacity;
    private int shelfCapacity;

    // Weight of each item 
    private int[] weightsData;

    // Category of each item 
    private int[] categoriesData;

    // limitCategories[c]: maximum number of items of category c on a shelf 
    private int[] limitCategories;

    // binAssignment[s]: list of bins assigned to shelf s 
    private int[][] binsAssignment;

    // Hexaly Optimizer 
    private final HexalyOptimizer optimizer;

    // Decision variables 
    private HxExpression[] bins;

    // Shelves (union of bins) 
    private HxExpression[] shelves;

   // Weight of each bin, shelf in the solution 
    private HxExpression[] binWeights;
    private HxExpression[] shelfWeights;

    // Whether the bin, shelf is used in the solution
    private HxExpression[] binsUsed;
    private HxExpression[] shelvesUsed;

    // Objectives
    private HxExpression totalBinsUsed;
    private HxExpression totalShelvesUsed;

    private ShelfPacking(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    // Read instance data 
    private void readInstance(String fileName) throws IOException {
        JsonReader reader = new JsonReader(new InputStreamReader(new FileInputStream(fileName)));
        JsonObject data = JsonParser.parseReader(reader).getAsJsonObject();

        nbItems = data.get("nbItems").getAsInt();
        nbCategories = data.get("nbCategories").getAsInt();
        nbShelves = data.get("nbShelves").getAsInt();
        nbMaxBins = nbItems;

        binCapacity = data.get("binCapacity").getAsInt();
        shelfCapacity = data.get("shelfCapacity").getAsInt();

        JsonArray weightsDataArray = (JsonArray) data.get("itemWeights");
        JsonArray categoriesDataArray = (JsonArray) data.get("itemCategories");
        weightsData = new int[nbItems];
        categoriesData = new int[nbItems];
        for (int i=0; i<nbItems; ++i){
            weightsData[i] = weightsDataArray.get(i).getAsInt();
            categoriesData[i] = categoriesDataArray.get(i).getAsInt();
        }

        JsonArray limitCategoriesArray = (JsonArray) data.get("limitCategories");
        limitCategories = new int[nbCategories];
        for (int i=0; i<nbCategories; i++){
            limitCategories[i] = limitCategoriesArray.get(i).getAsInt();
        }

        JsonArray binsAssignmentJsonArray = (JsonArray) data.get("binsAssignment");
        binsAssignment = new int[nbShelves][];
        int shelfIdx = 0;
        for (Object shelfAssignement : binsAssignmentJsonArray) {
            JsonArray shelfAssignmentArray = (JsonArray) shelfAssignement;
            binsAssignment[shelfIdx] = new int[shelfAssignmentArray.size()];
            for (int binIdx = 0; binIdx < shelfAssignmentArray.size(); ++binIdx){
                binsAssignment[shelfIdx][binIdx] = shelfAssignmentArray.get(binIdx).getAsInt();
           }
           shelfIdx++;
        }

    }

    private void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        bins = new HxExpression[nbMaxBins];
        shelves = new HxExpression[nbShelves];
        binWeights = new HxExpression[nbMaxBins];
        shelfWeights = new HxExpression[nbShelves];
        binsUsed = new HxExpression[nbMaxBins];
        shelvesUsed = new HxExpression[nbShelves];

        // Set decisions: bins[k] represents the items in bin k 
        for (int k = 0; k < nbMaxBins; ++k) {
            bins[k] = model.setVar(nbItems);
        }

        // Compute the union of bins on the same shelf to get all the items on this shelf
        for (int s = 0; s < nbShelves; ++s) {
            HxExpression shelf = model.union();
            for (int b : binsAssignment[s]) {
                shelf.addOperand(bins[b]);
            }
            shelves[s] = shelf;
        }

        // Constraint: Each item must be in one bin and one bin only 
        model.constraint(model.partition(bins));

        HxExpression weights = model.array(weightsData);
        HxExpression weightLambda = model.lambdaFunction(i -> model.at(weights, i));

        for (int k = 0; k < nbMaxBins; ++k) {
            // Constraint: Weight constraint on each bin 
            binWeights[k] = model.sum(bins[k], weightLambda);
            model.constraint(model.leq(binWeights[k], binCapacity));

            // Bin k is used if at least one item is in it
            binsUsed[k] = model.gt(model.count(bins[k]), 0);  
        }

        for (int s = 0; s < nbShelves; ++s) {
            // Constraint: the number of items per category on a shelf is limited
            shelfWeights[s] = model.sum(shelves[s], weightLambda);
            model.constraint(model.leq(shelfWeights[s], shelfCapacity));

            // Shelf s is used if at least one item is on it 
            shelvesUsed[s] = model.gt(model.count(shelves[s]), 0);

            for (int c = 0; c < nbCategories; ++c){
                HxExpression itemsPerCategory = model.array();
                for (int i = 0; i < nbItems; ++i) {
                    if (categoriesData[i] == c) {
                        itemsPerCategory.addOperands(i);
                    }
                }
                // Constraint: the number of items per category on a shelf is limited 
                HxExpression shelfIntersection = model.intersection(itemsPerCategory, shelves[s]);
                model.constraint(model.leq(model.count(shelfIntersection),limitCategories[c]));
            }

        }

        totalShelvesUsed = model.sum(shelvesUsed);
        totalBinsUsed = model.sum(binsUsed);

        // Minimize the number of used shelves (first objective) then bins (second objective) 
        model.minimize(totalShelvesUsed);
        model.minimize(totalBinsUsed);
        model.close();

        // Parametrize the optimizer 
        optimizer.getParam().setTimeLimit(limit);

        optimizer.solve();
    }

    // Write the output file  
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            for (int s = 0; s<nbShelves; ++s){
                if (shelvesUsed[s].getValue() != 0) {
                    output.print("Shelf "+ s +" total weight: " + shelfWeights[s].getValue() + "/" + shelfCapacity);
                    output.println();
                    for (int k = 0; k < nbMaxBins; ++k) {
                        if (binsUsed[k].getValue() != 0) {
                            output.print(">Bin weight: " + binWeights[k].getValue()+ "/" + binCapacity + " | Items: ");
                            HxCollection binCollection = bins[k].getCollectionValue();
                            for (int i = 0; i < binCollection.count(); ++i) {
                                output.print("#"+binCollection.get(i) + " ");
                            }
                            output.println();
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java ShelfPacking inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "5";

        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            ShelfPacking model = new ShelfPacking(optimizer);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}