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 such that all items are placed.

Hexaly Optimizer reaches an average gap of 0.30% in 60 seconds of running time on the Bin Packing Problem. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers, like Gurobi 9.1, on this basic but challenging problem.

Input data

BPPLIB is a reference benchmark for the Bin Packing Problem. We compare the results obtained by Hexaly and Gurobi 9.1 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 9.1 are obtained using the standard Mixed-Integer Programming model for the Bin Packing Problem, introduced in the seminal paper by Kantorovich and detailed in the book by Martello and Toth. 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 only 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;
}

Gurobi and Hexaly 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 10.5 and Gurobi 9.1, known as a state-of-the-art MIP solver. Both are used with default parameters. We ran our experiments on a server equipped with an Intel Core i7-6700k processor (4 cores, 4.0GHz, 8MB cache) and 64GB 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, even on the largest instances. After 1 minute, the worst gap observed for Hexaly over the 240 instances is 1.07%; after 10 minutes, its worst gap is 0.37%. After 1 minute, the average gap observed for Gurobi is 55%; after 10 minutes, its average gap is 30%.

Conclusion

Set modeling with Hexaly provides a compact model for the Bin Packing Problem (BPP), which yields a huge performance advantage. Indeed, near-optimal solutions are delivered in seconds for instances with thousands of items to pack. On the other hand, traditional MIP solvers like Gurobi struggle to find quality solutions to the problem, even for moderate-size instances.

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.

Share