Models and bounds for two-dimensional level packing problems
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(n log n) 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.
packing cutting ilp models