LocalSolver


Benchmark Bin-Packing

In the Bin Packing Problem (BPP), a number of items with known weights must be assigned to bins with uniform capacity. The objective is to minimize the number of bins used such that all items are placed.
On this page, we compare LocalSolver to classical MIP solvers on bin packing instances.


Data

The BPPLib is the reference corpus of bin packing instances.
In this benchmark we compare the results obtained by LocalSolver and its competitors for different solving times on 400 instances - the Falkenauer and GI instances of the BPPLib. Since the best known solutions to this problems are either optimal or close to optimality, our metric will be the relative gap to this best known solution.


Models

MIP model

The results reported below for commercial MIP solvers are obtained with the standard Mixed Integer Programming model for Bin Packing (introduced by Kantorovitch). It 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.

LocalSolver model

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 versatile than that of the MIP model. The number of variables is only linear, and we will see that it scales to much larger problems. The detailed model is available in LSP, Python, Java, C++ and .Net in our example tour.


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

    // Each item must be in one bin and one bin only
    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 at least one item is in it
        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;
}

Performance

We have measured the gap value regularly until 300 seconds. The comparison is made between LocalSolver 8.5 and a commercial MIP solver, both without any specific configuration or tuning. The BPP Library has more than 6000 bin packing instances, with 50 to more than 5000 items. We used the Falkenauer and GI datasets (160 and 240 instances respectively) which cover the whole range of instance sizes.

Below is a chart representing 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.

Both solvers reach a feasible solution almost immediately. LocalSolver obtains a very small gap in a matter of seconds even on the biggest instances, with an average gap around 1% after 10s. After 300s, the average gap is below 0,5% for all sizes. On the smallest instances, the MIP solver still has an average gap of 2% after 5 minutes, which is more than 4 times worse than LocalSolver. For bigger instances, the MIP solver is not able to improve over its first solution at all, and the gap remains above 20%. On some instances the MIP solver finds no feasible solution or exceeds available memory (8 Gb) . In both cases a symbol 'x' is reported on the graph.

Set modeling with LocalSolver provides a compact model for packing problems, which yields a huge performance advantage. For bin packing problems, its approach based on local search algorithms finds satisfying solutions almost immediately. Even on huge instances, where integer programming models are struggling, LocalSolver finds very good solutions in a matter of seconds.

Contact us - Disclaimer - Copyright 2019 Innovation 24