Bin Packing Problem (BPP)

import hexaly.optimizer
import sys
import math

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


def read_integers(filename):
    with open(filename) as f:
        return [int(elem) for elem in f.read().split()]


with hexaly.optimizer.HexalyOptimizer() as optimizer:
    # Read instance data
    file_it = iter(read_integers(sys.argv[1]))

    nb_items = int(next(file_it))
    bin_capacity = int(next(file_it))

    weights_data = [int(next(file_it)) for i in range(nb_items)]
    nb_min_bins = int(math.ceil(sum(weights_data) / float(bin_capacity)))
    nb_max_bins = min(nb_items, 2 * nb_min_bins)

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

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

    # 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)
    weight_lambda = model.lambda_function(lambda i: weights[i])

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

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

    # Count the used bins
    total_bins_used = model.sum(bins_used)

    # Minimize the number of used bins
    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

    # Stop the search if the lower threshold is reached
    optimizer.param.set_objective_threshold(0, nb_min_bins)

    optimizer.solve()

    # Write the solution in a file
    if len(sys.argv) >= 3:
        with open(sys.argv[2], 'w') as f:
            for k in range(nb_max_bins):
                if bins_used[k].value:
                    f.write("Bin weight: %d | Items: " % bin_weights[k].value)
                    for e in bins[k].value:
                        f.write("%d " % e)
                    f.write("\n")

#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;
    }
}

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: bin[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);
        }
    }
}

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))) {
            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);
        }
    }
}