Dual feasible functions

Objectives

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

It is also used by the Benders decomposition to generate cuts.

Principle

The algorithm builds dominated instances, in the sense that every feasible solution of the original instance is also feasible for the dominated instances. Computing the classical area bound on these instances may lead to different values, sometimes better, which remain valid bounds for the original instance.

In the example below, the bin is 10 × 6 and there are two copies each of items 1 (6 × 4), 2 (4 × 6) and 3 (4 × 3). Every pair of these items fits together in the bin, so the area bound (2 × (24 + 24 + 12) = 120, divided by the bin area 60, rounded up) is only 2:

../../_images/rectangle_dual_feasible_functions_instance.svg

We apply the following transformation:

  • the items of height at least 4 get the height 6;

  • the items of height at most 2 are removed.

Every feasible solution of the original instance is feasible for the modified instance: when the height of an item of height at least 4 is increased to the height of the bin, every item it might intersect has a height of at most 2, and is therefore among the removed items.

Only item 1 is affected by the transformation: its height becomes 6. Here is the dominated instance:

../../_images/rectangle_dual_feasible_functions_dominated_instance.svg

The area bound of the dominated instance (2 × (36 + 24 + 12) = 144, divided by 60, rounded up) is 3, which turns out to be tight: the original instance does require 3 bins.

Functions

Such transformations are dual feasible functions: a function \(f\) such that, for any set of lengths fitting in a capacity \(C\), the transformed lengths fit in \(f(C)\). The ones used are the three families of Carlier, Clautiaux and Moukrim (2007), each one parametrized by a breakpoint \(k \in [1, C / 2]\):

  • \(f_0\) rounds the long lengths up to the capacity and the short ones down to 0:

\[\begin{split}f_0(x) = \begin{cases} C & \text{if } x > C - k \\ x & \text{if } k \le x \le C - k \\ 0 & \text{if } x < k \end{cases}\end{split}\]

  • \(f_1\) counts the medium items, of length between \(k\) and \(C / 2\). Let \(M(c)\) be the maximum number of medium items fitting in a length \(c\), computed greedily from the shortest ones. A medium item counts for 1, a short item for 0, the capacity for \(M(C)\), and a long item for the number of medium items it displaces:

\[\begin{split}f_1(x) = \begin{cases} M(C) - M(C - x) & \text{if } x > C / 2 \\ 1 & \text{if } k \le x \le C / 2 \\ 0 & \text{if } x < k \end{cases}\end{split}\]

  • \(f_2\) rounds the lengths down to multiples of \(k\), counting the long lengths by the room they leave:

\[\begin{split}f_2(x) = \begin{cases} 2 \left( \lfloor C / k \rfloor - \lfloor (C - x) / k \rfloor \right) & \text{if } x > C / 2 \\ \lfloor C / k \rfloor & \text{if } x = C / 2 \\ 2 \lfloor x / k \rfloor & \text{if } x < C / 2 \end{cases}\end{split}\]

The figure below shows the three functions for \(C = 10\) and \(k = 3\), scaled so that \(f(C)\) is at the top (for \(f_1\), all the medium items have length 3). The dashed line is the identity, scaled the same way: the short lengths are mostly rounded down, and the long ones up.

../../_images/rectangle_dual_feasible_functions_functions.svg

In two dimensions. A function \(f\), with a breakpoint \(k\), is applied to the widths, with the width \(W\) of the bin as capacity, and a function \(g\), with a breakpoint \(l\), to the heights, with the height \(H\) of the bin as capacity. The transformed area of an item of size \(w \times h\) is \(f(w) \, g(h)\), and the one of the bin is \(f(W) \, g(H)\): for any packing of the original instance, the total transformed area of the items doesn’t exceed the transformed area of the bin. All the pairs of families \((f, g)\) are tried, with all the pairs of breakpoints \((k, l)\).

Breakpoints. The breakpoints tried for the widths are the widths \(w\) of the items not larger than \(W / 2\), the values \(W - w\) for the larger ones (the widths equal to \(W\) are skipped), and \(W / 2\). The same is done for the heights.

Bounds. For each pair of families and each pair of breakpoints:

  • bin-packing and feasibility: the bound is the total transformed area of the items divided by the transformed area of the bin, rounded up. The best bound is kept. For the feasibility objective, the instance is proven infeasible if the bound exceeds the number of bins.

  • knapsack: the bound is the fractional (Dantzig) bound of the knapsack problem with the transformed areas: the capacity is the transformed area of the bin times its number of copies, the items are sorted by decreasing profit per transformed area, and the last one is taken fractionally. An item whose transformed area is 0 is always taken; an item which doesn’t fit in the bin is never taken. The smallest bound is kept. Since the bound ignores the resources, the penalties of the penalize resources which increase the profit are added to it.

Rotations

When an item can be rotated, its transformed area depends on its orientation. Two strategies are used:

  • Smallest orientation. In the computation above, the smallest of the transformed areas of its two orientations is used, which keeps the bound valid whatever the orientation of the item in the packing. For \(f_1\), the dimension used to decide whether an item is medium is its smallest dimension which qualifies.

  • Doubled instance (Clautiaux, Jouglet and El Hayek, 2007), for the bin-packing and feasibility objectives only. An instance is built where the bin is a square of side \(\max(W, H)\), and each item type appears twice, once in each orientation, which can’t be rotated. A packing of the original instance in \(m\) bins gives a packing of this instance in \(2m\) bins: one in the original orientation and one rotated. So half the bound of this instance, rounded up, is a bound of the original instance. When the bin isn’t a square, the bound is computed again with, in each square bin, a dummy item filling the part of the square outside the original bin, as many times as the current bound, until the bound doesn’t increase anymore. The bound kept is the largest of the two strategies.

Cuts

For a selection of items assigned to a bin, the same functions give inequalities on the numbers of copies \(n_i\) of each item type, valid for any selection in a bin of this type:

\[\sum_i f(w_i) \, g(h_i) \, n_i \le f(W) \, g(H)\]

The Benders decomposition looks, for each selection proposed by its master problem, for the pair of families and the pair of breakpoints whose inequality is the most violated by the selection.

Automatic selection

The bound is computed automatically when there is a single bin type and at most 100 items. It can be forced with --use-dual-feasible-functions 1 (CLI) or use_dual_feasible_functions (Python).

Source files

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

  • scripts/doc_figures/rectangle_dual_feasible_functions.py: the figure of the functions

References: