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 

Digitization and the Internet of Things: The Convergence of Technology and Business Models
Markus Larsson
25 September 2016 - 27 September 2016 | Göteborg, Sweden
Conferences & Talks  

Human-Centered Designed Robots are All Around Us
Leila Takayama
29 September 2016
PARC Forum  

Stanford and PARC host Digital Cities Summit 2016
Victoria Bellotti, Panel Facilitator, Bernard Casse, Panelist, Sean Garner, Panelist, Stephen Hoover, Keynote Speaker, Matthew Klenk, Tolga Kurtoglu, Panel Facilitator, Markus Larsson, Speaker, Ersin Uzun, Panelist
3 October 2016 - 4 October 2016 | Stanford, CA
Conferences & Talks  

2016 Annual Conference of the Prognostics and Health Management Society
Parham Shahidi, Panelist, Rui Maranhão, Keynote Speaker
5 October 2016 - 6 October 2016 | Denver, CO
Conferences & Talks