Hexaly vs Gurobi on the Bin Packing Problem (BPP)

Benchmark Packing

Léa Optimization Scientist August 19, 2024

The Bin Packing Problem is defined as follows. You have to assign items with known weights to bins with uniform capacity. The sum of weights of items assigned to each bin must be lower than its capacity. The objective is to minimize the number of bins used to place all items.

On the Bin Packing Problem (BPP), Hexaly reaches an average gap of 0.1% in 1 minute on the BPPLIB research benchmark. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers, like Gurobi 11.0, on this fundamental but challenging problem.

Input data

BPPLIB is a reference benchmark for the Bin Packing Problem. We compare the results obtained by Hexaly 13.0 and Gurobi 11.0 for different solving times on the most recent, hardest, and largest instances proposed by Gschwind and Irnich in 2016. Since the best known solutions are not proven optimal for all the considered instances, our metric is the relative gap in % to the best solution known by the research.

Mathematical models of the Bin Packing Problem

Mixed-Integer Linear Programming (MILP) model

The results reported below for Gurobi 11.0 are obtained using the standard Mixed-Integer Linear Programming (MILP) model for the Bin Packing Problem (BPP), introduced in Kantorovish’s seminal paper and detailed in Martello and Toth’s book. This formulation consists of a quadratic number of binary variables representing the assignment of an item to a bin and one binary variable per bin representing whether the bin is used or not.

Hexaly model

The Hexaly model uses one set variable per bin, representing the items allocated to the bin. The demand for each item is retrieved by the at operator. This formulation is more compact and versatile than the MILP formulation. The number of variables is linear; we will show that it scales to large-scale instances.

function model() {
    // Set decisions: bins[k] contains the items assigned to bin k
    bins[k in 0..nbMaxBins-1] <- set(nbItems);

    // Each item must be assigned to one and only one bin
    constraint partition[k in 0..nbMaxBins-1](bins[k]);
    
    for [k in 0..nbMaxBins-1] {
        // Weight constraint for each bin
        binWeights[k] <- sum(bins[k], i => itemWeights[i]);
        constraint binWeights[k] <= binCapacity;
    
        // Bin k is used if it contains at least one item
        binsUsed[k] <- (count(bins[k]) > 0);
    }
    
    // Count the used bins
    totalBinsUsed <- sum[k in 0..nbMaxBins-1](binsUsed[k]);

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

Hexaly and Gurobi results on the Bin Packing Problem

We compare both solvers’ performance within 1 minute of running time. At the end of the running time, we measure the gap in % to the best solutions known in the literature, also called State Of The Art (SOTA). The comparison is made between Hexaly 13.0 and Gurobi 11.0, a state-of-the-art MILP solver. Both are used with default parameters. We ran our experiments on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM. BPPLIB contains more than 6,000 bin-packing instances. We used the most recent dataset, namely “GI”, composed of 240 instances proposed by Gschwind and Irnich in 2016. They are the largest-scale instances in BPPLIB, with 1,212 to 5,486 items to pack.

The table below presents the average gap between feasible solutions found by each solver and the SOTA grouped by instance family. For each family, we provide the minimum and maximum number of items.

Both solvers reach a feasible solution almost immediately. Hexaly delivers solutions close to the SOTA in seconds. After 1 minute, the worst gap observed for Hexaly over the 240 instances is 0.4%. After 1 minute, the average gap observed for Gurobi is 44%.

Conclusion

Hexaly’s set decision variables offer a natural and compact modeling approach to the Bin Packing Problem (BPP). With thousands of items to pack, Hexaly delivers near-optimal solutions in seconds. On the other hand, traditional MILP solvers like Gurobi struggle to find quality solutions with hundreds of items to pack.

You can find the complete model of the Bin Packing Problem (BPP) and many others in Python, Java, C#, and C++ in our Example Tour.