home › event - optimal packing of high-precision rectangles


Optimal Packing of High-Precision Rectangles
Conferences & Talks



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.


upcoming events   view all 

Disruptive Technologies in Manufacturing (Opening Keynote)
Stephen Hoover
28 April 2015 | Seattle, WA
Conferences & Talks  

The First Five Kilobytes are the Hardest
George Dyson
29 April 2015 | George E. Pake Auditorium, PARC
PARC Forum  

Printed Hybrid Logic Circuits
Janos Veres
29 April 2015 | Berlin, Germany
Conferences & Talks  

IoT User Experience Design
Mike Kuniavsky
12 May 2015 | San Francisco, CA
Conferences & Talks  

CCNxCon 2015
Glenn Edens, Bill Janssen, Marc Mosko, Glenn Scott, Dick Sillman, Nacho Solis, Chris Wood, Yali Wang
18 May 2015 - 21 May 2015 | Palo Alto, CA
Conferences & Talks