Colored Bin Packing Problem (CBPP)

# Copyright (c) Hexaly. Permission is hereby granted to use, copy,
# and modify this code for applications developed with Hexaly.
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 = next(file_it)
    nb_colors = next(file_it)
    bin_capacity = next(file_it)
    weights_data = []
    colors_data = []

    for _ in range(nb_items):
        weights_data.append(next(file_it))
        colors_data.append(next(file_it))

    nb_min_bins = int(math.ceil(sum(weights_data) / float(bin_capacity)))
    nb_max_bins = nb_items

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

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

    # Transform bins list into HxExpression
    bins_array = model.array(bins)

    # Each item must be in exactly one bin
    model.constraint(model.partition(bins))

    # Create an array and a function to retrieve item's weight and color
    weights = model.array(weights_data)
    weight_lambda = model.lambda_function(lambda i: weights[i])
    colors = model.array(colors_data)
    color_lambda = [model.lambda_function(lambda j: colors[j] == i ) for i in range(nb_colors)]

    # 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)
    
    # At most one item of each color per bin
    nb_colors_per_bin = [[model.sum(b, color_lambda_i) for color_lambda_i in color_lambda] for b in bins]
    for bin in nb_colors_per_bin:
        for nb_color in bin:
            model.constraint(nb_color <= 1)


    # 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 > 0:
                    f.write("Bin weight: %d | Items: " % bin_weights[k].value)
                    for e in bins[k].value:
                        f.write("%d " % e)
                    f.write("\n")

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
#include "optimizer/hexalyoptimizer.h"
#include <cmath>
#include <fstream>
#include <iostream>
#include <numeric>
#include <vector>

using namespace hexaly;
using namespace std;

class ColoredBinPacking {
private:
    // Number of items
    int nbItems;

    // Number of colors
    int nbColors;

    // 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;

    // Color of each item;
    std::vector<hxint> colorsData;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    std::vector<HxExpression> bins;

    // Weight of each bin in the solution
    std::vector<HxExpression> binWeights;

    // Number of elements of each color in each bin
    std::vector<std::vector<HxExpression>> nbElementsOfColorInBin;

    // 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 >> nbColors;
        infile >> binCapacity;

        weightsData.resize(nbItems);
        colorsData.resize(nbItems);
        for (int i = 0; i < nbItems; ++i) {
            infile >> weightsData[i];
            infile >> colorsData[i];
        }

        nbMinBins = ceil(accumulate(weightsData.begin(), weightsData.end(), 0.0) / binCapacity);
        nbMaxBins = nbItems;
    }

    void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        bins.resize(nbMaxBins);
        binWeights.resize(nbMaxBins);
        binsUsed.resize(nbMaxBins);
        nbElementsOfColorInBin.resize(nbMaxBins, std::vector<HxExpression>(nbColors));
        
        // 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]; });

        // Create an array and a function to retrieve the item's color
        HxExpression colors = model.array(colorsData.begin(), colorsData.end());
        std::vector<HxExpression> colorLambda(nbColors);
        for (int k = 0; k < nbColors; k++)
            colorLambda[k] = model.createLambdaFunction([&](HxExpression i) { return (colors[i] == k); });

        for (int k = 0; k < nbMaxBins; ++k) {
            // Weight constraint for each bin
            binWeights[k] = model.sum(bins[k], weightLambda);
            model.constraint(binWeights[k] <= binCapacity);
    
            // At most one item of each color per bin
            for (int i = 0; i < nbColors; i++){
                nbElementsOfColorInBin[k][i] = model.sum(bins[k], colorLambda[i]);
                model.constraint(nbElementsOfColorInBin[k][i] <= 1);
            }
            // 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: colored_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 {
        ColoredBinPacking 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;
    }
}

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
using System;
using System.IO;
using System.Linq;
using Hexaly.Optimizer;

public class ColoredBinPacking : IDisposable
{
    // Number of items
    int nbItems;

    // Number of colors
    int nbColors;

    // Capacity of each bin
    int binCapacity;

    // Maximum number of bins
    int nbMaxBins;

    // Minimum number of bins
    int nbMinBins;

    // Weight of each item
    long[] weightsData;

    // Color of each item
    long[] colorsData;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression[] bins;

    // Weight of each bin in the solution
    HxExpression[] binWeights;

    // Number of elements of each color in each bin
    HxExpression[][] nbElementsOfColorInBin;

    // Whether the bin is used in the solution
    HxExpression[] binsUsed;

    // Objective
    HxExpression totalBinsUsed;

    public ColoredBinPacking()
    {
        optimizer = new HexalyOptimizer();
    }

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] firstline = input.ReadLine().Split();
            nbItems = int.Parse(firstline[0]);
            nbColors = int.Parse(firstline[1]);
            binCapacity = int.Parse(firstline[2]);

            weightsData = new long[nbItems];
            colorsData = new long[nbItems];

            for (int i = 0; i < nbItems; ++i){
                string[] splitted = input.ReadLine().Split();
                weightsData[i] = int.Parse(splitted[0]);
                colorsData[i] = int.Parse(splitted[1]);
            }
            nbMinBins = (int)Math.Ceiling((double)weightsData.Sum() / binCapacity);
            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];
        binWeights = new HxExpression[nbMaxBins];
        binsUsed = new HxExpression[nbMaxBins];
        nbElementsOfColorInBin = new HxExpression[nbMaxBins][];

        for (int k = 0; k < nbMaxBins; k++){
            nbElementsOfColorInBin[k] = new HxExpression[nbColors];
        }

        // 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]);

        HxExpression colors = model.Array(colorsData);

        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;

            // At most one item of each color per bin
            for (int i = 0; i < nbColors; i++){
                HxExpression colorlambda_i = model.LambdaFunction( l => (colors[l] == i));
                nbElementsOfColorInBin[k][i] = model.Sum(bins[k], colorlambda_i);
                model.Constraint(nbElementsOfColorInBin[k][i] <= 1);
            }
        }

        // 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: ColoredBinPacking 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 (ColoredBinPacking model = new ColoredBinPacking())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class ColoredBinPacking {
    // Number of items
    private int nbItems;

    // Number of colors;
    private int nbColors;

    // 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;

    // Color of each item
    private long[] colorsData;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Decision variables
    private HxExpression[] bins;

    // Weight of each bin in the solution
    private HxExpression[] binWeights;

    // Number of elements of each color in each bin
    private HxExpression[][] nbElementsOfColorInBin;

    // Whether the bin is used in the solution
    private HxExpression[] binsUsed;

    // Objective
    private HxExpression totalBinsUsed;

    private ColoredBinPacking(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();
            nbColors = input.nextInt();
            binCapacity = input.nextInt();

            weightsData = new long[nbItems];
            colorsData = new long[nbItems];
            for (int i = 0; i < nbItems; ++i) {
                weightsData[i] = input.nextInt();
                colorsData[i] = input.nextInt();
            }

            long sumWeights = 0;
            for (int i = 0; i < nbItems; ++i) {
                sumWeights += weightsData[i];
            }

            nbMinBins = (int) Math.ceil((double) sumWeights / binCapacity);
            nbMaxBins = 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];
        nbElementsOfColorInBin = new HxExpression[nbMaxBins][nbColors];

        // 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));

        HxExpression colors = model.array(colorsData);
        HxExpression[] colorLambda = new HxExpression[nbColors];
        
        for (int k = 0; k < nbColors; ++k){
            final int j = k;
            colorLambda[k] = model.lambdaFunction(l -> model.eq( model.at(colors, l), j));
        }

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


            // At most one item of each color per bin
            for (int i = 0; i < nbColors; ++i){
                nbElementsOfColorInBin[k][i] = model.sum(bins[k], colorLambda[i]);
                model.constraint(model.leq(nbElementsOfColorInBin[k][i], 1));
            }

            // 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 ColoredBinPacking 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()) {
            ColoredBinPacking model = new ColoredBinPacking(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);
        }
    }
}