A branch and bound algorithm for the strip packing problem

A branch and bound algorithm for the strip packing problem

0.00 Avg rating0 Votes
Article ID: iaor200950404
Country: Germany
Volume: 31
Issue: 2
Start Page Number: 431
End Page Number: 459
Publication Date: Apr 2009
Journal: OR Spectrum
Authors: , ,
Keywords: programming: branch and bound
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.