home › event - optimal packing of high-precision rectangles

EVENT:

Optimal Packing of High-Precision Rectangles
Conferences & Talks

 

description

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 

Aston Martin: The Brand Journey of a 100 Year-old Startup
Mr. Simon Sproule
29 August 2016
PARC Forum  

A Low-cost and Innovative Radar “Digital Eye”
Bernard Casse
20 September 2016 - 22 September 2016 | Brussels, Belgium
Conferences & Talks  

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