rectangle algorithms¶
See rectangle for the input/output format and CLI usage of this solver.
Tree search¶
This algorithm solves the feasibility, knapsack, open-dimension-x, open-dimension-y, bin-packing and bin-packing-with-leftovers objectives.
It is a tree search algorithm where a single item is packed at each stage. The root node is an empty partial solution (no item packed). Given a node, a child node is generated for each feasible insertion of each unpacked item, either in the same bin or in a new bin.
The possible insertions for an unpacked item are the ones where the new item is packed above either a packed item or the bottom of the bin, then shifted right until it intersects no packed item.
Tree search with maximal spaces¶
This algorithm solves the feasibility and knapsack objectives with a single bin, and the bin-packing, bin-packing-with-leftovers, open-dimension-x and open-dimension-y objectives through sequential feasibility.
It doesn’t support unloading constraints.
It is a tree search algorithm where a block of items is packed at each stage. The blocks (grids of copies of an item type, and their combinations) are generated first. A node stores the maximal empty rectangles of the bin; its children place each block fitting in the empty rectangle closest to a corner of the bin. A node is evaluated by completing it greedily.
Benders decomposition¶
This algorithm solves the knapsack, bin-packing and variable-sized-bin-packing objectives exactly.
Its master problem assigns the items to the bins considering only their areas, as a one-dimensional problem. For each bin of its solution, a subproblem checks whether the items actually fit; if not, cuts forbidding this selection of items are added to the master problem, which is solved again.
Benders decomposition with contiguity¶
This algorithm solves the knapsack and feasibility objectives exactly, for a single bin.
Its master problem also decides the x-positions of the items (contiguous relaxation), and its subproblem only searches y-positions consistent with them.
Dual feasible functions¶
This algorithm computes a bound for the bin-packing, feasibility and knapsack objectives, for instances with a single bin type.
It builds dominated instances, in which every feasible solution of the original instance remains feasible, by transforming the dimensions of the items and of the bin; the area bound of the dominated instances is a valid bound, sometimes better than the one of the original instance.
Conservative scales¶
This algorithm computes a bound for the bin-packing and feasibility objectives, for instances with a single bin type and without item rotation.
It optimizes new dimensions for the items with linear programs, such that the packings remain feasible, and computes the area bound with them.
Bar relaxation¶
This algorithm computes a bound for the knapsack, feasibility, bin-packing and variable-sized-bin-packing objectives.
It slices the bins into unit rows and columns, and only requires that the items can be distributed among them; the resulting linear program is solved by column generation.