Packages
fixpoint
0.17.3
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
data/bin_packing/bin_packing/BinPacking.java
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;
public class BinPacking {
// Number of items
private int nbItems;
// Capacity of each bin
private int binCapacity;
// Maximum number of bins
private int nbMaxBins;
// Minimum number of bins
private int nbMinBins;
// Weight of each item
private long[] weightsData;
// Hexaly Optimizer
private final HexalyOptimizer optimizer;
// Decision variables
private HxExpression[] bins;
// Weight of each bin in the solution
private HxExpression[] binWeights;
// Whether the bin is used in the solution
private HxExpression[] binsUsed;
// Objective
private HxExpression totalBinsUsed;
private BinPacking(HexalyOptimizer optimizer) {
this.optimizer = optimizer;
}
/* Read instance data */
private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
input.useLocale(Locale.ROOT);
nbItems = input.nextInt();
binCapacity = input.nextInt();
weightsData = new long[nbItems];
for (int i = 0; i < nbItems; ++i) {
weightsData[i] = input.nextInt();
}
long sumWeights = 0;
for (int i = 0; i < nbItems; ++i) {
sumWeights += weightsData[i];
}
nbMinBins = (int) Math.ceil((double) sumWeights / binCapacity);
nbMaxBins = Math.min(2 * nbMinBins, nbItems);
}
}
private void solve(int limit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
bins = new HxExpression[nbMaxBins];
binWeights = new HxExpression[nbMaxBins];
binsUsed = new HxExpression[nbMaxBins];
// Set decisions: bins[k] represents the items in bin k
for (int k = 0; k < nbMaxBins; ++k) {
bins[k] = model.setVar(nbItems);
}
// Each item must be in one bin and one bin only
model.constraint(model.partition(bins));
// Create an array and a lambda function to retrieve the item's weight
HxExpression weights = model.array(weightsData);
HxExpression weightLambda = model.lambdaFunction(i -> model.at(weights, i));
for (int k = 0; k < nbMaxBins; ++k) {
// Weight constraint for 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);
}
// Count the used bins
totalBinsUsed = model.sum(binsUsed);
// Minimize the number of used bins
model.minimize(totalBinsUsed);
model.close();
// Parametrize the optimizer
optimizer.getParam().setTimeLimit(limit);
// Stop the search if the lower threshold is reached
optimizer.getParam().setObjectiveThreshold(0, nbMinBins);
optimizer.solve();
}
/* Write the solution in a file */
private void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
for (int k = 0; k < nbMaxBins; ++k) {
if (binsUsed[k].getValue() != 0) {
output.print("Bin weight: " + binWeights[k].getValue() + " | 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 BinPacking 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()) {
BinPacking model = new BinPacking(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);
}
}
}