LP-Based Heuristics for Conservative Scales in Orthogonal Packing
Authors: G. Belov, H. Rohling, G. Scheithauer
Preprint MATH-NM-06-2009
The \emph{$d$-Dimensional Orthogonal Packing Problem} (OPP-$d$, $d\ge2$) asks whether all given boxes can be orthogonally packed into a given container without rotations. Many solution methods use \emph{bounds on the solution value}. For example, the simplest bound for OPP is the \emph{volume bound}: if the total volume of the items exceeds that of the container then the instance is infeasible. \emph{Conservative scales} (CS) are modified item sizes such that if OPP is feasible, it is also feasible with the modified sizes. Thus, the volume bound for the modified instance is valid for the original instance. Up to now, CS have been constructed either (i) completely independently in each dimension using \emph{dual-feasible functions} or (ii) by an exact method in the 2D case. Between (i) and (ii), there are possible heuristic algorithms which construct $d$ conservative scales (in $d$ dimensions) simultaneously. Our first efforts in this direction have shown that a simple LP iteration produces results nearly identical with the exact method in smaller time. 3D results are presented as well. Keywords: packing, relaxation, conservative scales, dual-feasible functions
Preprint version: PDF