Optimal packing of high-precision rectangles

Details

Event Twenty-Fifth Conference on Artificial Intelligence (AAAI-11)

Authors

Eric Huang
Technical Publications
August 7th 2011
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.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

FIND OUT MORE
Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.

FIND OUT MORE
News

PARC scientists and staffers are active members and contributors to the science and technology communities.

FIND OUT MORE