Hexaly vs Gurobi on the Bin Packing Problem

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, Hexaly reaches an average gap of 0.2% 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 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 to these problems are either optimal or close to optimality, our metric is the relative gap to this best known solution.

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 Programming model for the Bin Packing Problem, 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 MIP formulation. The number of variables is linear; we will show that it scales to much larger 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 with two solving times: 1 minute and 10 minutes. At the end of the running time, we measure the gap to the best known solution in %. The comparison is made between Hexaly 12.5 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 instances in BPPLIB, with 1,212 to 5,486 items to pack.

Below is a chart detailing the results. The instance size is on the horizontal axis, and the gap to the best known solution is on the vertical axis. Results for different time limits can be selected with the slider.

Both solvers reach a feasible solution almost immediately. Hexaly delivers solutions with small gaps in seconds. After 1 minute, the worst gap observed for Hexaly over the 240 instances is 0.6%; after 10 minutes, its worst gap is 0.3%. After 1 minute, the average gap observed for Gurobi is 44%; after 10 minutes, its average gap is 11%.


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. Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will gladly discuss your optimization problems.