Lower-dimensional bounds and a new model for higher-dimensional orthogonal packing
Authors: G. Belov, G. Scheithauer.
In: Ufa International Winter School-Conference in Maths and Physics for Students and Young Scientists. Lectures, Volume 5. Bashkirian State University, Ufa, Russia. 2006. pp. 181-186.
Consider the feasibility problem in higher-dimensional orthogonal packing. Given a set $I$ of $d$-dimensional rectangles, we need to decide whether a feasible packing in an $d$-dimensional rectangular container is possible. No item rotation is allowed and item edges are parallel to the coordinate axes. Typically, solution methods employ some bounds to facilitate the decision. Various bounds are known, e.g.\ volume bounds, Lagrangian and/or continuous relaxation of ILP models, dual feasible functions, dimension reduction. We generalize two types of one-dimensional bounds. The first type leads to \emph{contiguous 1D stock cutting}, where items of each type are situated in consecutive bins. The second type leads to standard 1D stock cutting, we call it \emph{bar relaxation}. The first type allows the construction of a new type of model for orthogonal packing which shares the combinatorial structure of the models of \citet{FekExact} and \citet{Kar99}. We compare the strength of the bounds of both types and present some numerical results.