Optimal Rectangle Packing: An Absolute Placement Approach

The authors consider the problem of finding all enclosing rectangles of minimum area that can contain a given set of rectangles without overlap. Their rectangle packer chooses the x-coordinates of all the rectangles before any of the y-coordinates. They then transform the problem into a perfect-packing problem with no empty space by adding additional rectangles. To determine the y-coordinates, they branch on the different rectangles that can be placed in each empty position. Their packer allows them to extend the known solutions for a consecutive-square benchmark from 27 to 32 squares. They also introduce three new bench-marks, avoiding properties that make a benchmark easy, such as rectangles with shared dimensions. Their third benchmark consists of rectangles of increasingly high precision.

Provided by: AI Access Foundation Topic: Software Date Added: Jan 2013 Format: PDF

Find By Topic