Sequential feasibility

Objectives

This algorithm solves the bin-packing, bin-packing-with-leftovers, open-dimension-x, open-dimension-y, open-dimension-z (box) and open-dimension-xy (irregular) objectives with an algorithm solving the feasibility objective. It is not selected by itself: the algorithms which only solve the feasibility objective use it for the other objectives.

Principle

It solves a sequence of feasibility sub-problems, asking whether all the items fit into a shrinking space:

  • bin-packing: the first \(k\) bins of the instance;

  • bin-packing-with-leftovers: the first \(k\) bins, the last one cut to a length \(L\);

  • open-dimension-x, open-dimension-y and open-dimension-z: the bin cut to a length \(L\) along the open dimension;

  • open-dimension-xy: a bin of width \(L\) and of height \(L\) times the aspect ratio.

The first space is large: twice the space of the items. As long as a sub-problem is solved, the solution found is reported, and the next space is smaller than the space this solution actually uses. The algorithm stops as soon as a sub-problem isn’t solved: the inner algorithm proves it infeasible, or doesn’t find a solution within its effort. The last solution found is the result.

In the example below, the open dimension is x, the strip has a height of 2, and the items have a height of 1: the first length is twice the area of the items (18) divided by the height of the strip, 18. The first solution uses a length of 10, so the next length is 9; the second solution uses a length of 9, so the next length is 8, for which the inner algorithm finds no solution:

../../_images/generic_algorithms_sequential_feasibility.svg

First space

  • bin-packing and bin-packing-with-leftovers: the smallest number of first bins of the instance whose space is at least twice the space of the items (at least 1); for bin-packing-with-leftovers, the last of these bins is not cut at first;

  • open dimensions: twice the space of the items divided by the section of the bin (e.g. its height for open-dimension-x), at most the length of the bin;

  • open-dimension-xy (irregular): the items are first packed in columns by a simple procedure, which gives a first solution; the first width is the width of this solution, shrunk by the shrink ratio below.

For irregular, the space of an item is the area of its bounding box.

Shrinking

After a solution is found:

  • bin-packing: \(k\) is one less than the number of bins the solution uses;

  • open dimensions: \(L\) is the length used by the solution along the open dimension, shrunk: for rectangle, rectangleguillotine and box, \(\min(\lfloor 0.99 \, \ell \rfloor, \ell - 1)\) for a length used \(\ell\); for irregular, \((1 - r) \, \ell\) with the shrink ratio \(r\) (1% by default, 0.1% for the local search), plus the minimum spacing between the items and the bin;

  • bin-packing-with-leftovers: \(L\) is the length used in the last bin, shrunk the same way. If the solution uses fewer bins than available, \(k\) becomes its number of bins and the last bin isn’t cut; if \(L\) reaches 0, \(k\) is decreased by one, and the new last bin isn’t cut. The last bin is cut along the direction of the leftover: along x for rectangleguillotine and irregular, along the direction of the leftover mode for rectangle (y for the mode Y, otherwise x) and box (its first dimension: z for the mode Z, y for the modes Y and YZ, otherwise x);

  • open-dimension-xy (irregular): the width is shrunk by the shrink ratio, and at most the width of a bin of the given aspect ratio with the area of the bounding box of the solution.

The algorithm also stops when nothing is left to try: no bin, or a length of 0. For irregular, the bins up to the last one with fixed items are always kept, since a sub-problem without them would turn their fixed items into free items.

Warm start. For irregular, each sub-problem, except the first one, receives the previous solution found as a warm start. It is generally not a feasible solution of the sub-problem: the space has been shrunk, so some items may stick out of their bin, and the bins which aren’t available anymore are dropped together with their items. It is up to the inner algorithm to repair it, and the irregular local search does.

Uses

The MILP assignment and column generation algorithms use a similar scheme for the bin-packing objective, but in the opposite direction: they try the numbers of bins in increasing order from a lower bound, so that the first feasible one is optimal.

Source files

  • src/irregular/sequential_feasibility.hpp, src/irregular/sequential_feasibility.cpp

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

  • src/rectangleguillotine/sequential_feasibility.hpp, src/rectangleguillotine/sequential_feasibility.cpp

  • src/box/sequential_feasibility.hpp, src/box/sequential_feasibility.cpp

  • scripts/doc_figures/generic_algorithms.py, scripts/doc_figures/generic_algorithms_model.py: the figure, with a simple inner algorithm (a depth-first search placing the items in two rows)