rectangle-guillotine algorithms

See rectangleguillotine for the input/output format and CLI usage of this solver.

Tree search with maximal spaces

This algorithm solves the feasibility and knapsack objectives.

It generates unlimited-staged guillotine patterns.

It is a tree search algorithm where multiple items are packed at each stage.

In a first step, some blocks of items are generated. Blocks may contain a single item, multiple items of the same type, or multiple items of different types. Here is an example of block generation from 4 items:

../_images/rectangleguillotine_tree_search_maximal_spaces_1.png

In a node of the branching scheme, all maximal empty rectangles are stored. To generate the children of a node, a maximal empty rectangle is first selected, then one child is generated for each remaining block that fits inside the considered space.

At the root node, the only maximal empty rectangle is the bin itself, so two children are generated per candidate block, one with a vertical cut and one with a horizontal cut:

../_images/rectangleguillotine_tree_search_maximal_spaces_2.png

Placing a block can leave more than one maximal empty rectangle. Here are the two maximal empty rectangles of the first child generated above:

../_images/rectangleguillotine_tree_search_maximal_spaces_3.png

In the rectangle-guillotine case, the maximal empty rectangles don’t overlap.

When generating the children of this node, one of these maximal empty rectangles is selected, and one child is generated per remaining block that fits inside:

../_images/rectangleguillotine_tree_search_maximal_spaces_4.png

References:

Column generation strips

This algorithm solves the knapsack, open-dimension-x and open-dimension-y objectives.

It generates k-staged guillotine patterns. It is fast when k = 2. When k >= 4, it becomes impractical.

It is a tree search algorithm where a whole strip is packed at each stage. Contrary to the tree search maximal spaces algorithm, the strips are not generated beforehand, but dynamically in the nodes through column generation.

The column generation model is as follows:

Input:

  • a bin of width \(W\)

  • item types \(j = 1, \ldots, n\); for each item type \(j\): a profit \(p_j\), a width \(w_j\) and a number of copies \(q_j\)

  • a set \(K\) of feasible first-level sub-plate patterns (“strips”); for each pattern \(k \in K\), \(x_j^k\) is the number of copies of item type \(j\) it contains

Variables:

  • \(y^k \in \{0, \ldots, q^{\max}\}\), \(k \in K\): number of times sub-plate pattern \(k\) is used

Objective: maximize the total profit of the packed items

\[\max \sum_{k} \Big( \sum_{j} p_j \, x_j^k \Big) y^k\]

Constraints:

  • Bin width: the sub-plates selected must fit side by side in the bin

\[\sum_{k} \Big( \max_{j} w_j x_j^k \Big) y^k \le W\]

  • Item demand: each item type used at most \(q_j\) times

\[\forall j \qquad \sum_{k} x_j^k \, y^k \le q_j\]

The pricing sub-problem consists in finding a sub-plate pattern of negative reduced cost

\[rc(y^k) = \Big( \max_{j} w_j x_j^k \Big) u + \sum_{j} x_j^k v_j - \sum_{j} p_j x_j^k\]

where \(u\) and \(v_j\) are the dual variables of the bin width and item demand constraints. This is solved for every possible sub-plate width, by recursively solving \((k-1)\)-staged guillotine single-knapsack sub-problems – one-dimensional knapsack problems for 2-stage exact, 2-stage non-exact or 3-stage homogeneous instances, and the same algorithm applied recursively otherwise. Also yields knapsack / open-dimension bounds.

Here is an illustration of the algorithm:

../_images/rectangleguillotine_column_generation_strips.png

Sequential strips / one-dimensional

This algorithm solves the bin-packing and bin-packing-with-leftovers objectives.

It is a two-phase heuristic:

  1. Generate a set of strips by solving a strip-packing problem (pack all items, minimize total width).

  2. Solve a one-dimensional bin packing problem where each strip becomes an “item” (its width becomes the item length, and the bin width becomes the item length capacity), to decide how strips are grouped into bins.

Contrary to the tree search maximal spaces algorithm and the column generation strips algorithm, the generated strips contain exactly all the items.

../_images/rectangleguillotine_sequential_strips_onedimensional.png

Tree search hypergraph

This algorithm solves the feasibility and knapsack objectives.

It generates unlimited-staged guillotine patterns.

This is a kind of tree search algorithm, but instead of generating children from one parent node, children are generated from two parent nodes. A node corresponds to a partial packing. For two given parent nodes, two child nodes are generated by combining the two parents either vertically or horizontally.

This is similar to the block generation step of the tree search maximal spaces algorithm. In the tree search maximal spaces algorithm, the block generation stops once enough blocks have been generated; while in this algorithm, the block generation stops when it actually generates a block that is the optimal solution.

../_images/rectangleguillotine_labelling.png

Tree search hypergraph with infinite copies

This algorithm solves the feasibility and knapsack objectives.

It generates unlimited-staged guillotine patterns.

This algorithm works the same way as the tree search hypergraph algorithm, except that the item type quantities are not taken into account. This means that the domination rule is cheaper to compute and prunes many more nodes. Therefore, it is very fast, but the generated solution might be infeasible regarding the available number of item copies.

../_images/rectangleguillotine_dynamic_programming_infinite_copies.png

Dual feasible functions

This algorithm computes a bound for the bin-packing objective.

See rectangle