Bin Packing Problem with Conflicts (BPPC)

import hexaly.optimizer
import sys
import math

if len(sys.argv) < 2:
    print("Usage: python bin_packing_conflicts.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
    filename = sys.argv[1]
    count = 0
    weights_data = []
    forbidden_items = []
    with open(filename) as f:
        for line in f:
            line = line.split()
            if count == 0:
                nb_items = int(line[0])
                bin_capacity = int(line[1])
            else:
                weights_data.append(int(line[1]))
                forbidden_items.append([])
                for i in range(2, len(line)):
                    forbidden_items[count-1].append(int(line[i]))
            count += 1
                    
    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: bins[k] represents the items in bin k
    bins = [model.set(nb_items) for _ in range(nb_max_bins)]

    # Transform bins and itemFordbidden list into hx expression
    bins_array = model.array(bins)
    forbidden_items_array = model.array(forbidden_items)

    # Find the bin where an item is packed
    bin_for_item = [model.find(bins_array, i) for i in range(nb_items)]

    # 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])

    # Forbidden constraint for each items
    for i in range(nb_items):
        items_intersection = model.intersection(forbidden_items_array[i], bins_array[bin_for_item[i]])
        model.constraint(model.count(items_intersection) == 0)

    # 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_items):
                f.write("item:%d Weight:%d" % (k, weights_data[k]))
                f.write("\n")
            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 BinPackingConflicts {
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;

    // List of forbidden items
    std::vector<std::vector<int>> forbiddenItems;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

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

    // Bin where the item is
    std::vector<HxExpression> binForItem;

    // 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) {
        int count = 0;
        ifstream infile(fileName);
        infile >> nbItems;
        infile >> binCapacity;
        weightsData.resize(nbItems);
        infile.ignore(numeric_limits<streamsize>::max(), '\n');
        string line;
        while (getline(infile, line)) {
            istringstream ss(line);
            std::vector<string> lineParts;
            string part;
            while (ss >> part) {
                lineParts.push_back(part);
            }
            weightsData[count] = stoi(lineParts[1]);
            forbiddenItems.push_back(std::vector<int>());
            for (size_t i = 2; i < lineParts.size(); ++i) {
                forbiddenItems[count].push_back(stoi(lineParts[i]));
            }
            ++count;
        }
        infile.close();

        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);
        HxExpression binsArray = model.array();
        HxExpression forbiddenItemsArray = model.array();

        // Set decisions: bins[k] represents the items in bin k
        for (int k = 0; k < nbMaxBins; ++k) {
            bins[k] = model.setVar(nbItems);
            binsArray.addOperand(bins[k]);
        }

        for (int i = 0; i < nbItems; ++i) {
            forbiddenItemsArray.addOperand(model.array(forbiddenItems[i].begin(), forbiddenItems[i].end()));
        }

        // Find the bin where an item is packed
        binForItem.resize(nbItems);
        for (int i = 0; i < nbItems; ++i) {
            binForItem[i] = model.find(binsArray, i);
        }

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

        // Forbidden constraint for each items
        for (int i = 0; i < nbItems; ++i) {
            HxExpression itemsIntersection = model.intersection(binsArray[binForItem[i]], forbiddenItemsArray[i]);
            model.constraint(model.count(itemsIntersection) == 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 {
        BinPackingConflicts 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 System.Collections.Generic;
using Hexaly.Optimizer;

public class BinPackingConflicts : 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;

    // List of forbidden items
    private List<List<int>> forbiddenItems;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression[] bins;

    // Bin where the item is
    private HxExpression[] binForItem;

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

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

    // Objective
    HxExpression totalBinsUsed;

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

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        int count = 0;
            using (StreamReader input = new StreamReader(fileName))
            {
                forbiddenItems = new List<List<int>>();
                string firstLine = input.ReadLine();
                string[] firstLineParts = firstLine.Split(' ');
                nbItems = int.Parse(firstLineParts[0]);
                binCapacity = int.Parse(firstLineParts[1]);
                weightsData = new long[nbItems];

                string line;
                while ((line = input.ReadLine()) != null)
                {
                    string[] lineParts = line.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                    weightsData[count] = long.Parse(lineParts[1]);
                    forbiddenItems.Add(new List<int>());
                    for (int i = 2; i < lineParts.Length; ++i)
                    {
                        forbiddenItems[count].Add(int.Parse(lineParts[i]));
                    }
                    count++;
                }
            }
        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];
        HxExpression binsArray = model.Array();
        HxExpression forbiddenItemsArray = model.Array();

        // Set decisions: bins[k] represents the items in bin k
        for (int k = 0; k < nbMaxBins; ++k)
        {
            bins[k] = model.Set(nbItems);
            binsArray.AddOperand(bins[k]);
        }

        for (int i = 0; i < nbItems; ++i)
        {
            forbiddenItemsArray.AddOperand(model.Array(forbiddenItems[i]));
        }

        // Find the bin where an item is packed
        binForItem = new HxExpression[nbItems];
        for (int i = 0; i < nbItems; ++i) {
            binForItem[i] = model.Find(binsArray, i);
        }

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

        // Forbidden constraint for each items
        for (int i = 0; i < nbItems; ++i)
        {
            HxExpression itemsIntersection = model.Intersection(binsArray[binForItem[i]], forbiddenItemsArray[i]);
            model.Constraint(model.Count(itemsIntersection) == 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: BinPackingConflicts 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 (BinPackingConflicts model = new BinPackingConflicts())
        {
            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 BinPackingConflicts {
    // 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;

    // List of forbidden items
    private List<List<Integer>> forbiddenItems;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Decision variables
    private HxExpression[] bins;

    // Bin where the item is
    private HxExpression[] binForItem;

    // 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 BinPackingConflicts(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        int count = 0;
        try (Scanner input = new Scanner(new File(fileName))) {
            nbItems = input.nextInt();
            binCapacity = input.nextInt();
            weightsData = new long[nbItems];
            forbiddenItems = new ArrayList<>();
            input.nextLine();
            while (input.hasNextLine()) {
                String line = input.nextLine();
                String[] lineParts = line.split("\\s+");
                weightsData[count] = Integer.parseInt(lineParts[1]);
                forbiddenItems.add(new ArrayList<>());
                for (int i = 2; i < lineParts.length; ++i) {
                    forbiddenItems.get(count).add(Integer.parseInt(lineParts[i]));
                }
                count++;
            }

            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];
        HxExpression binsArray = model.array();
        HxExpression forbiddenItemsArray = model.array();

        // Set decisions: bins[k] represents the items in bin k
        for (int k = 0; k < nbMaxBins; ++k) {
            bins[k] = model.setVar(nbItems);
            binsArray.addOperand(bins[k]);
        }

        for (int i = 0; i < nbItems; ++i) {
            forbiddenItemsArray.addOperand(model.array(forbiddenItems.get(i)));
        }

        // Find the bin where an item is packed
        binForItem = new HxExpression[nbItems];
        for (int i = 0; i < nbItems; ++i) {
            binForItem[i] = model.find(binsArray, i);
        }

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

        // Forbidden constraint for each items
        for (int i = 0; i < nbItems; ++i) {
            HxExpression itemsIntersection = model.intersection(model.at(binsArray, binForItem[i]),
                    model.at(forbiddenItemsArray, i));
            model.constraint(model.eq(model.count(itemsIntersection), 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 BinPackingConflicts 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()) {
            BinPackingConflicts model = new BinPackingConflicts(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);
        }
    }
}