A branch and bound algorithm for the strip packing problem

We propose a new branch and bound algorithm for the two dimensional strip packing problem, in which a given set of rectangular pieces have to be packed into a strip of given width and infinite length so as to minimize the required height of the packing. We develop lower bounds based on integer formulations of relaxations of the problem as well as new bounds based on geometric considerations, and reduce the tree search with some dominance criteria. An extensive computational study shows the relative efficiency of the bounds and the good performance of the exact algorithm.