Shelf Packing Problem
PackingProblem
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
- Work with JSON files
- Add set decision variables to model the contents of the bins
- Use the union operator to model the contents of the shelves
- Define a lambda function to compute the total weight of bins and shelves
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\pythonpython shelfpacking.py instances/instance_0.json
- Execution (Linux)
-
export PYTHONPATH=/opt/hexaly_14_0/bin/pythonpython 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.libShelfPacking 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.dllShelfPacking 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.jarjava -cp %HX_HOME%\bin\hexaly.jar;. ShelfPacking instances\instance_0.json
- Compilation / Execution (Linux)
-
javac BinPackingConflicts.java -cp /opt/hexaly_14_0/bin/hexaly.jarjava -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);
}
}
}