Hexaly, Gurobi, OR-Tools on the Bin Packing Problem with Conflicts (BPPC)

Benchmark Packing

Inès Optimization Scientist February 4, 2025

In the Bin Packing Problem with Conflicts (BPPC), a number of items with known weights must be assigned to bins with uniform capacity. For each item, one has a list of incompatible items that cannot be put together in the same bin. The objective is to minimize the number of bins used so that all items are placed, and no incompatible items are put together in the same bin. It is a typical example of an NP-hard problem. Bin Packing Problems (BPP) occur in many industrial fields, such as transportation, logistics, manufacturing, and telecommunications. Considering conflicts between items allows better modeling of real-life problems where it is not always possible to pack together items. The model for the regular Bin Packing Problem is available in our Example Tour.

On the Bin Packing Problem with Conflicts (BPPC), Hexaly reaches a 0.5% average gap to the best known solutions in the literature in 1 minute of running time on the Muritiba BPPC benchmark. This article illustrates how Hexaly performs compared with Mixed-Integer Linear Programming (MILP) solvers like Gurobi and Constraint Programming (CP) solvers like OR-Tools, commonly used to solve such problems in business and industry.

Input data

A comprehensive set of instances for the BPPC used by Muritiba (2010) is available here. The set contains 800 instances and is divided into eight classes, as proposed by Falkenauer (1996) for the Bin Packing Problem (BPP). The set offers test cases ranging from 60 to 1000 items to pack. The conflicts are obtained by assigning a probability p to each item according to a continuous uniform distribution on [0,1] and then creating a conflict between items i and j if :

where d = 0%, 10%, …, 90%.

Mathematical models of the Bin Packing Problem with Conflicts (BPPC)

Gurobi and OR-Tools models

The results reported for Gurobi and OR-Tools are obtained using the formulation described in Gendreau (2004) with their Python APIs. It consists of a quadratic number of binary variables representing the assignment of each item to each bin and a linear number of binary variables representing whether each bin contains at least one item.

Hexaly model

The Hexaly model for the Bin Packing Problem with Conflicts (BPPC) uses one set variable per bin. The packing of all items is ensured through a partition constraint. We compute the total weight of a bin using a lambda function to sum weights over all the items packed in the bin. Preventing items in conflict from being put in the same bin is ensured with an empty intersection constraint between the bin containing an item and all its incompatible items. Finally, the number of used bins is computed by counting the number of non-empty bins with the count operator.

function model() {
    // Set decisions : bins[k] represents the items in bin k 
    bins[k in 0...nBins] <- set(nItems); 
    
    // Each item must be in one bin and one bin only
    constraint partition[k in 0...nbins](bins[k]);

    for [k in 0...nBins] {
        // Weight constraint for each bin
        binWeight[k] <- sum(bins[k], i => weight[i]);
        constraint binWeight[k] <= binCapacity;     
    }

    for [item in itemList] {
        local binItem <- find(bins, item);
        local incompatItems <- incompatibleItems[item];
        // Incompatible items cannot be put together in a bin
        constraint count(intersection(bins[binItem], incompatItems) == 0; 
    }

    // Count the used bins
    binUsed[k in 0...nBins] <- count(bins[k]) > 0 ;
    totalBinsUsed <- sum(binUsed);

    // Minimize the number of used bins
    minimize totalBinsUsed;
}

Hexaly, Gurobi, OR-Tools results on the Bin Packing Problem with Conflicts (BPPC)

We compare all solvers’ performance within 1 minute of running time on the Muritiba instances with up to 1,000 items. At the end of the resolution, we measure the gap in % to the best solutions known in the literature, also called state-of-the-art (SOTA) solutions. These solutions are available here. Note that these SOTA solutions are computed using dedicated algorithms with arbitrarily long running times on specific hardware.

We use Hexaly 13.5, Gurobi 11.0, and OR-Tools 9.11, each with default parameters. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM. The table below presents the average gap between feasible solutions found by each solver and the SOTA, as reported here. We report infeasible solutions with a 100% gap.

Hexaly finds solutions close to best known solutions for instances with up to 1,000 items in less than 1 minute. OR-Tools delivers poor-quality solutions (> 50% gap on average) and fails to find feasible solutions on large-scale instances. Gurobi also fails to find feasible solutions in 1 minute of running time for some instance classes.

Conclusion

Hexaly offers an innovative modeling approach based on set variables, count and intersection operators, and partition constraints, making the mathematical modeling of the Bin Packing Problem with Conflicts (BPPC) straightforward. The resulting model for the BPPC is compact and natural while providing much better and faster results than state-of-the-art Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP) solvers like Gurobi and OR-Tools.