LocalSolver


Benchmark — Bin Packing Problem (BPP)

The Bin Packing Problem (BPP) 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. Here we show how LocalSolver 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 LocalSolver 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 will be the relative gap to this best known solution.

Mathematical models

The results reported below for Gurobi 9.1 are obtained using the standard Mixed-Integer Programming model for 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.

The LocalSolver model uses one set variable per bin, representing the items allocated to the bin. The demand of 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, and 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;
}

Results

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 LocalSolver 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 given in BPPLIB, with from 1,212 to 5,486 items to pack.

Both solvers reach a feasible solution almost immediately. LocalSolver delivers solutions with small gaps in a matter of seconds, even on the largest instances. After 1 minute, the worst gap observed for LocalSolver over the 240 instances is 1.1%; after 10 minutes, its worst gap is 0.4%. After 1 minute, the average gap observed for Gurobi is 55%; after 10 minutes, its average gap is 30%.

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

Conclusion

Set modeling with LocalSolver provides a compact model for the Bin Packing Problem (BPP), which yields a huge performance advantage: 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) in Python, Java, C#, and C++, and LSP in our Example Tour.

We are at your disposal to accompany you in the discovery of LocalSolver. Don't hesitate to contact us for any further information or support.

Contact us - Disclaimer - Privacy policy - Copyright 2021 LocalSolver