Conservative scales

Objectives

This algorithm computes a bound for the bin-packing and feasibility objectives, for instances with a single bin type and without item rotation. It doesn’t produce solutions.

Principle

It computes the bound \(L_{BKRS}\) of Belov, Kartak, Rohling and Scheithauer (2013), as used by Côté, Haouari and Iori (2021).

Like the dual feasible functions, it replaces the dimensions of the items by other values, keeping the packings feasible, and computes the area bound of the transformed instance. But the new widths are not given by a formula: they are optimized, and they take into account the heights.

Conservative scales. New widths \(w'_j\) are conservative if, for every set of items whose original widths sum to at most the width \(W\) of the bin, their new widths also sum to at most \(W\). Then any set of items which can be crossed by a horizontal line in a packing still fits along the width with the new widths, so the area bound computed with the new widths is still valid.

Linear program. Among the conservative scales, the ones maximizing the transformed area are computed by a linear program.

Input:

  • the width \(W\) of the bin

  • the item copies \(j = 1, \ldots, N\) (one per copy of each item type); for each item copy \(j\): its original width \(w_j\) and a weight \(h_j\), its current height (the original one, or a rescaled one)

  • the sets \(S\) of item copies whose original widths sum to at most \(W\): \(\sum_{j \in S} w_j \le W\)

Variables:

  • \(w'_j \ge 0\): the new width of item copy \(j\) (0 for the item copies wider than the bin)

Objective: maximize the transformed area

\[\max \sum_j h_j \, w'_j\]

Constraints:

  • Conservative scales: the item copies fitting along the width with their original widths still fit with their new widths

\[\forall S \qquad \sum_{j \in S} w'_j \le W\]

There are exponentially many constraints, so they are generated by a cutting-plane loop: the linear program is solved with the constraints found so far, then the most violated constraint for its solution is found by solving a 0-1 knapsack problem (the item copies with their new widths as profits and their original widths as weights, of capacity \(W\)) with the onedimensional algorithms. If its optimal value exceeds \(W\), its solution is a violated constraint, which is added; otherwise, the solution is optimal. The new heights are computed the same way, exchanging the widths and the heights.

Iterations. The first vectors are the original widths and heights. At each iteration, new widths are optimized with the heights of the previous iteration as weights, and new heights with the widths of the previous iteration as weights. Each new vector of widths (resp. heights) is combined with all the vectors of heights (resp. widths) computed so far, and the bound is the best area bound over all these pairs:

\[\left\lceil \frac{\sum_j w'_j \, h'_j}{W H} \right\rceil\]

By default, 5 iterations are performed. The iterations stop earlier if an iteration gives the same widths and heights as the previous one. The cutting-plane loop of a linear program stops after 10000 rounds at most; the original widths (or heights), which are conservative, are then used instead.

For the feasibility objective, the instance is proven infeasible if the bound exceeds the number of bins.

The items must not be rotatable: with rotations, the scales of an item would depend on its orientation, and treating an item as fixed in its given orientation could overstate the bound.

Automatic selection

The bound is computed automatically when there is a single bin type, no item can be rotated, and there are at most 100 items. It can be forced with use_conservative_scales (Python, C++); there is no CLI option.

Source files

  • src/rectangle/conservative_scales.hpp, src/rectangle/conservative_scales.cpp

References: