Optimal Rectangle Packing: Initial Results

Given a set of rectangles with fixed orientations, we want to find an enclosing rectangle of minimum area that contains them all with no overlap. Many simple scheduling tasks can be modelled by this NP-complete problem. We use an anytime branch-and-bound algorithm to solve the problem optimally. Our main contributions are a lower-bound on the amount of wasted space in a partial solution, based on a relaxation of the problem to one-dimensional bin packing, and a dominance condition that allows us to ignore many partial solutions. For our experiments, we choose a class of increasingly difficult square-packing problems as a simple and easily-specified benchmark. The square-packing problem of size N is to find the smallest rectangle that contains the 1x1, 2x2, etc. up to NxN square. We find optimal solutions to these problems up to size N=22. For comparison, we also find the best slicing solutions, a popular approximation algorithm. Our approach is rather general, and many of our techniques can be applied to packing non-rectangular shapes in non-rectangular enclosing regions, and higher-dimensional packing problems as well.

Authors

• Richard E. Korf

Keywords

No keywords are indexed for this paper.