Packages
fixpoint
0.21.2
0.22.2
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.cs
using System;
using System.IO;
using System.Linq;
using Hexaly.Optimizer;
public class BinPacking : IDisposable
{
// 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
long[] weightsData;
// Hexaly Optimizer
HexalyOptimizer optimizer;
// Decision variables
HxExpression[] bins;
// Weight of each bin in the solution
HxExpression[] binWeights;
// Whether the bin is used in the solution
HxExpression[] binsUsed;
// Objective
HxExpression totalBinsUsed;
public BinPacking()
{
optimizer = new HexalyOptimizer();
}
/* Read instance data */
void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
nbItems = int.Parse(input.ReadLine());
binCapacity = int.Parse(input.ReadLine());
weightsData = new long[nbItems];
for (int i = 0; i < nbItems; ++i)
weightsData[i] = int.Parse(input.ReadLine());
nbMinBins = (int)Math.Ceiling((double)weightsData.Sum() / binCapacity);
nbMaxBins = Math.Min(2 * nbMinBins, 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];
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.Set(nbItems);
// 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
HxExpression weights = model.Array(weightsData);
HxExpression weightLambda = model.LambdaFunction(i => 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);
// 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 */
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
for (int k = 0; k < nbMaxBins; ++k)
{
if (binsUsed[k].GetValue() != 0)
{
output.Write("Bin weight: " + binWeights[k].GetValue() + " | 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: BinPacking 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 (BinPacking model = new BinPacking())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}