Optimal packing of high-precision rectangles

The rectangle-packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. We propose a new benchmark that includes rectangles of successively higher precision. This challenges the previous state-of-the-art solver, which enumerates all locations of placing rectangles, as well as all bounding box widths and heights up to the optimal box. We improve this by limiting the rectangles coordinates and bounding box dimensions to the set of subset sums of the rectangles dimensions. We also dynamically prune future value assignments by learning from previously infeasible subtrees, and widen the rectangles, which constrains the problem more. Compared to the previous state-of-the-art, we test 4,500 times fewer bounding boxes on the high-precision benchmark, solve N=9 over two orders of magnitude faster, and present all optimal solutions up to N=15, an instance requiring 39 bits of precision to represent. Finally, we provide the first published computational results on the open problem of packing an infinite series of rectangles into the unit square. We pack the first 50,000 rectangles of the series with a greedy heuristic and conjecture that the entire infinite series can fit.

Citation

Huang, E.; Korf, R. E. Optimal packing of high-precision rectangles. Twenty-Fifth Conference on Artificial Intelligence (AAAI-11); 2011 August 7-11; San Francisco, CA.