Packages
fixpoint
0.17.1
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/bin_packing.cpp
#include "optimizer/hexalyoptimizer.h"
#include <cmath>
#include <fstream>
#include <iostream>
#include <numeric>
#include <vector>
using namespace hexaly;
using namespace std;
class BinPacking {
private:
// Number of items
int nbItems;
// Capacity of each bin
int binCapacity;
// Maximum number of bins
int nbMaxBins;
// Minimum number of bins
int nbMinBins;
// Weight of each item
std::vector<hxint> weightsData;
// Hexaly Optimizer
HexalyOptimizer optimizer;
// Decision variables
std::vector<HxExpression> bins;
// Weight of each bin in the solution
std::vector<HxExpression> binWeights;
// Whether the bin is used in the solution
std::vector<HxExpression> binsUsed;
// Objective
HxExpression totalBinsUsed;
public:
/* Read instance data */
void readInstance(const string& fileName) {
ifstream infile;
infile.exceptions(ifstream::failbit | ifstream::badbit);
infile.open(fileName.c_str());
infile >> nbItems;
infile >> binCapacity;
weightsData.resize(nbItems);
for (int i = 0; i < nbItems; ++i) {
infile >> weightsData[i];
}
nbMinBins = ceil(accumulate(weightsData.begin(), weightsData.end(), 0.0) / binCapacity);
nbMaxBins = min(2 * nbMinBins, nbItems);
}
void solve(int limit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
bins.resize(nbMaxBins);
binWeights.resize(nbMaxBins);
binsUsed.resize(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.begin(), bins.end()));
// Create an array and a function to retrieve the item's weight
HxExpression weights = model.array(weightsData.begin(), weightsData.end());
HxExpression weightLambda = model.createLambdaFunction([&](HxExpression i) { return weights[i]; });
for (int k = 0; k < nbMaxBins; ++k) {
// Weight constraint for 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;
}
// Count the used bins
totalBinsUsed = model.sum(binsUsed.begin(), binsUsed.end());
// 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, (hxint)nbMinBins);
optimizer.solve();
}
/* Write the solution in a file */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.exceptions(ofstream::failbit | ofstream::badbit);
outfile.open(fileName.c_str());
for (int k = 0; k < nbMaxBins; ++k) {
if (binsUsed[k].getValue()) {
outfile << "Bin weight: " << binWeights[k].getValue() << " | 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: bin_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 {
BinPacking 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;
}
}