Heuristic and exact methods for the strip packing problem

The Two-Dimensional Strip Packing Problem (2SP) appears in many industries (like steel and paper industries) and consists in cutting a rectangular master surface, called strip, with a given width and infinite height into a number of rectangular pieces, each with a given size. The pieces must be cut with their edges always parallel or orthogonal to the edges of the master surface (orthogonal cuts) and we assume that items cannot be rotated, i.e. items have a fixed orientation. The objective is to minimize the total height of the strip. In this paper we propose lower and upper bounds and an exact algorithm. The proposed upper bounds are "constructive heuristics" based on different strategies to place the items into the strip. While, the new lower bounds are both combinatorial bounds and derived from different relaxations of the mathematical formulation of the 2SP. The new exact method makes use of new lower and upper bounds proposed in this paper and is based on a branch and bound approach. Computational results are reported for different sets of test problems derived from the literature. The computational experiments show the effectiveness of the new lower and upper bounds and of the new exact algorithm.