Models and bounds for two-dimensional level packing problems

Models and bounds for two-dimensional level packing problems

0.00 Avg rating0 Votes
Article ID: iaor2005534
Country: Netherlands
Volume: 8
Issue: 3
Start Page Number: 363
End Page Number: 379
Publication Date: Sep 2004
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: programming: linear
Abstract:

We consider two-dimensional bin packing and strip packing problems where the items have to be packed by levels. We introduce new mathematical models involving a polynomial number of variables and constraints, and show that their LP relaxations dominate the standard area relaxations. We then propose new (combinatorial) bounds that can be computed in O(nlogn) time. We show that they dominate the other bounds, and establish their absolute worst-case behavior. The quality of models and bounds is evaluated through extensive computational experiments.

Reviews

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