Bin Packing with Conflicts (BPPC)¶

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