An Exact Method for the 2D Guillotine Strip Packing Problem

Abstract EN

We consider the two-dimensional strip packing problem with guillotine cuts.

The problem consists in packing a set of rectangular items on one strip of width W and infinite height.

The items packed without overlapping must be extracted by a series of cuts that go from one edge to the opposite edge (guillotine constraint).

To solve this problem, we use a dichotomic algorithm that uses a lower bound, an upper bound, and a feasibility test algorithm.

The lower bound is based on solving a linear program by introducing new valid inequalities.

A new heuristic is used to compute the upper bound.

Computational results show that the dichotomic algorithm, using the new bounds, gives good results compared to existing methods.