Bar relaxation

Objectives

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

It is also used by the Benders decomposition to lift its no-good cuts.

Principle

It is the bar relaxation of Scheithauer (1999), in two dimensions, generalized to several bins of possibly different bin types. Instead of requiring a 2D placement of the items, each bin is sliced into unit-height horizontal row-bars, one-dimensional bins of capacity the width of the bin, and into unit-width vertical column-bars, one-dimensional bins of capacity the height of the bin. An item of width \(w\) and height \(h\) placed in the bin crosses \(h\) row-bars, taking a length \(w\) in each, and \(w\) column-bars, taking a length \(h\) in each. The relaxation only requires that the items packed can be distributed among the bars this way, which is a necessary condition for a packing.

In the figure below, the packing (left) gives 4 row-bars of capacity 6 (middle) and 6 column-bars of capacity 4 (right). Item A, of size 4 × 2, takes a length 4 in 2 row-bars, and a length 2 in 4 column-bars. The relaxation forgets which bars an item uses, as long as the bars aren’t overfilled: the pieces of an item don’t have to be in consecutive bars, nor at the same position in each bar.

../../_images/rectangle_bar_relaxation_bars.svg

Model

Input:

  • bin types \(t = 1, \ldots, m\); for each bin type \(t\): a width \(W_t\), a height \(H_t\), a cost \(c_t\), and a minimum and a maximum number of copies \(m_t\) and \(M_t\)

  • item types \(j = 1, \ldots, n\); for each item type \(j\): a profit \(p_j\) and a number of copies \(q_j\); an item type which can be rotated is split into two oriented variants; for each oriented variant \(i\): its width \(w_i\) and its height \(h_i\), and \(j(i)\) its item type

  • for each bin type \(t\), the row patterns \(q\), sets of oriented variants whose widths sum to at most \(W_t\), and the column patterns \(p\), sets of oriented variants whose heights sum to at most \(H_t\); \(a_{iq}\) (resp. \(b_{ip}\)) is the number of copies of variant \(i\) in pattern \(q\) (resp. \(p\))

Variables:

  • \(k_t \ge 0\): number of bins of type \(t\) used

  • \(n_{i,t} \ge 0\): number of copies of oriented variant \(i\) packed in bins of type \(t\)

  • \(y_q^t \ge 0\): number of row-bars of bin type \(t\) filled with row pattern \(q\)

  • \(x_p^t \ge 0\): number of column-bars of bin type \(t\) filled with column pattern \(p\)

Objective: depending on the objective

\[\max \sum_{i,t} p_{j(i)} \, n_{i,t} \qquad \text{(knapsack)}\]
\[\min \sum_t c_t \, k_t \qquad \text{(bin packing, variable-sized bin packing)}\]

For the feasibility objective, there is no objective: only the constraints.

Constraints:

  • Row-bars: an item of height \(h_i\) crosses \(h_i\) row-bars

\[\forall i, t \qquad \sum_q a_{iq} \, y_q^t = h_i \, n_{i,t}\]

  • Column-bars: an item of width \(w_i\) crosses \(w_i\) column-bars

\[\forall i, t \qquad \sum_p b_{ip} \, x_p^t = w_i \, n_{i,t}\]

  • Number of row-bars: a bin of height \(H_t\) has \(H_t\) row-bars

\[\forall t \qquad \sum_q y_q^t \le H_t \, k_t\]

  • Number of column-bars: a bin of width \(W_t\) has \(W_t\) column-bars

\[\forall t \qquad \sum_p x_p^t \le W_t \, k_t\]

  • Number of bins

\[\forall t \qquad m_t \le k_t \le M_t\]

  • Item copies: each item type is packed at most (knapsack) or exactly (other objectives) its number of copies

\[\forall j \qquad \sum_{i : j(i) = j} \; \sum_t n_{i,t} \le q_j\]

Solution method

The patterns are generated by column generation. The pricing problem of the row patterns (resp. column patterns) of a bin type is a knapsack problem over the oriented variants fitting in the bin type, of capacity \(W_t\) (resp. \(H_t\)), where each variant has the number of copies of its item type and, as profit, the dual value of its row-bar (resp. column-bar) constraint; the variants with a non-positive profit are left out. It is solved with the onedimensional algorithms.

Before the column generation converges, a valid bound is already available: the value of the current linear program, corrected by the reduced cost of the best row pattern and of the best column pattern of each bin type, times the maximum number of row-bars (resp. column-bars) of this bin type.

The optimal value of the linear program is a bound: a profit bound for the knapsack objective, a cost bound for the variable-sized-bin-packing objective, converted into a number of bins for the bin-packing objective. For the feasibility objective, an infeasible linear program proves that the instance is infeasible.

The defects and the fixed items are not modeled. Dropping them only relaxes the problem, so the bounds stay valid, but they may be weaker on the instances where they matter.

Automatic selection

It is computed automatically with a single bin, a single bin type of width and height at most 100, and the knapsack or feasibility objective (the size of the model grows with the dimensions of the bins). It can be forced with --use-bar-relaxation 1 (CLI) or use_bar_relaxation (Python).

Source files

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

  • scripts/doc_figures/rectangle_bar_relaxation.py: the figure of this page

References: