Journal
OR SPECTRUM
Volume 31, Issue 2, Pages 431-459Publisher
SPRINGER
DOI: 10.1007/s00291-008-0128-5
Keywords
Strip packing; Non-guillotine cutting; Branch and bound; Lower bounds
Categories
Funding
- Spanish Ministry of Science and Technology [DPI2005-04796, PBI-05-022]
- Consejeria de Ciencia y Tecnologia, Junta de Comunidades de Castilla-La Mancha
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available