Hexaly, Gurobi, OR-Tools on the Vector Bin Packing Problem (VBP)

Benchmarks Packing

Capucine Optimization Scientist August 18, 2025

In the Vector Bin Packing Problem (VBP), we pack multiple items, each with multiple attributes (dimensions), into identical bins. The goal is to determine the minimum number of bins necessary to pack all items while respecting capacity constraints in each dimension. The Hexaly model for the regular Bin Packing Problem is available in our Example Tour.

For the Vector Bin Packing (VBP) problem, Hexaly delivers optimal solutions for all instances within 1 minute of runtime. Gurobi and OR-Tools perform well on small-scale instances but struggle to find high-quality solutions as the problem size increases.

Input data

The Vector Bin Packing (VBP) instances used to compare the three solvers come from three sets of industrial data, originally sourced from the Google ROADEF/EURO Challenge. They have been adapted to suit the Vector Bin Packing Problem. You can download the modified instances here.

The sets offer test cases ranging from 100 to 50,000 items to pack, with items having from 2 to 12 dimensions. The maximum number of bins needed (nbMaxBins) is estimated using a First Fit algorithm. The First Fit algorithm for the Vector Bin Packing Problem (VBP) assigns each item to the first available bin with enough capacity in all dimensions. It processes items one by one, checking existing bins before opening a new one. If an item fits within an already opened bin, it is placed there, and its remaining capacity is updated. If no bin can accommodate the item, a new bin is created.

This approach limits the number of bins considered, preventing the analysis of models with extreme dimensions, such as 50,000 x 50,000, where preprocessing times for all three solvers vary significantly. Additionally, for many instances, no solutions are found within the 1-minute time limit, further complicating a fair comparison of their effectiveness.

Mathematical models for the Vector Bin Packing (VBP)

Gurobi and OR-Tools models

The results reported for Gurobi are obtained by running the MILP formulation presented in Alves et al. The OR-Tools model is adapted from the bin packing example.

Hexaly model

The Hexaly model for Vector Bin Packing (VBP) uses one set variable per possible bin. A partition constraint ensures the assignment of all items. It computes the total weight of each bin in every dimension using a lambda function that sums the weights of all the items packed in the bin. It then ensures that each bin respects the capacity constraints in each dimension by applying the and operator. Finally, it calculates the number of non-empty bins using the count operator.

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

    // Each item must be in one bin and one bin only
    constraint partition(bins);

    for [k in 0...nbMaxBins] {
        // Weight constraint for each bin and each dimension
        binWeights[k][d in 0...nbDimension] <- sum(bins[k], i => itemWeights[d][i]);
        constraint and[d in 0...nbDimension](binWeights[k][d] <= binCapacity[d]);

        // 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](binsUsed[k]);

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

Hexaly, Gurobi, OR-Tools results on the Vector Bin Packing Problem (VBP)

We compare the performance of three solvers—Hexaly 14.0, Google OR-Tools 9.12 (CP-SAT), and Gurobi 11.0—within a 1-minute runtime, using their default parameters. The tests were conducted on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB of RAM. In the following table, we present the gap, expressed in %, relative to the lower bound, which is determined by taking the maximum of the bounds across all dimensions. Specifically, for each dimension, the lower bound is calculated as the total sum of item sizes divided by the bin capacity. To enhance readability, we grouped the instances by size. For each group, the gap reported in the table represents the arithmetic mean of the percentage gaps across all instances within the group. We report infeasible solutions with a 100% gap.

Hexaly consistently delivers optimal solutions for instances with up to 50,000 items in under 1 minute. In contrast, OR-Tools and Gurobi provide strong solutions for smaller instances, but their performance deteriorates as instance size increases. OR-Tools fails to produce feasible solutions for instances larger than 20,000 items within one minute of runtime. Gurobi only finds a heuristic solution equivalent to the maximum number of bins, set by the First Fit algorithm. Beyond 20,000 items, both solvers completely fail to produce any solution.