# Optimal Rectangle Packing: Initial Results

@inproceedings{Korf2003OptimalRP, title={Optimal Rectangle Packing: Initial Results}, author={Richard E. Korf}, booktitle={ICAPS}, year={2003} }

Given a set of rectangles with fixed orientations, we want to find an enclosing rectangle of minimum area that contains them all with no overlap. Many simple scheduling tasks can be modelled by this NP-complete problem. We use an anytime branch-and-bound algorithm to solve the problem optimally. Our main contributions are a lower-bound on the amount of wasted space in a partial solution, based on a relaxation of the problem to one-dimensional bin packing, and a dominance condition that allows… Expand

#### 55 Citations

Optimal Rectangle Packing: New Results

- Computer Science, Mathematics
- ICAPS
- 2004

A new lower bound on the amount of wasted space in a partial solution, a new dominance condition that prunes many partial solutions, and a new algorithms to packing unoriented rectangles on the problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles are presented. Expand

Optimal rectangle packing

- Mathematics, Computer Science
- Ann. Oper. Res.
- 2010

This work considers the NP-complete problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles, and presents two different constraint-satisfaction formulations of this problem that dramatically outperform previous approaches to optimal rectangle packing. Expand

Optimal Rectangle Packing: An Absolute Placement Approach

- Mathematics, Computer Science
- J. Artif. Intell. Res.
- 2013

These algorithms represent the current state-of-the-art for this problem, outperforming other algorithms by orders of magnitude, depending on the benchmark, and introduce three new benchmarks, avoiding properties that make a benchmark easy, such as rectangles with shared dimensions. Expand

Optimal Rectangle Packing on Non-Square Benchmarks

- Computer Science
- AAAI
- 2010

Two new benchmarks are proposed, one where the orientation of the rectangles is fixed and one where it is free, that include rectangles of various aspect ratios that are much more difficult for the previous state-of-the-art solver. Expand

New Improvements in Optimal Rectangle Packing

- Mathematics, Computer Science
- IJCAI
- 2009

This work transforms the rectangle packing problem into a perfect packing problem that has no empty space, and presents inference rules to reduce the instance size. Expand

Almost Square Packing

- Mathematics, Computer Science
- CPAIOR
- 2011

This work extends the previously studied square packing problem by adding an additional degree of freedom for each rectangle, deciding in which orientation the item should be packed, and derives a decomposition method that initially only looks at the subproblem given by one of the cumulative constraints. Expand

Search Strategies for Rectangle Packing

- Mathematics, Computer Science
- CP
- 2008

It is argued that rectangle packing is a domain where constraint programming significantly outperforms hand-crafted ad-hoc systems developed for this problem, and this approach has other advantages over the state-of-the-art, such as being trivially modifiable to exploit multi-core computing platforms to parallelise search. Expand

Optimal Rectangle Packing: A Meta-CSP Approach

- Computer Science, Mathematics
- ICAPS
- 2006

A new approach to optimal rectangle packing, an NP-complete problem that can be used to model many simple scheduling tasks, is presented, and a suite of new techniques that exploit both the symmetry and geometry present in this particular domain are developed. Expand

Optimal Packing of High-Precision Rectangles

- Computer Science, Mathematics
- SOCS
- 2011

This work packs the first 50,000 such rectangles with a greedy heuristic and conjecture that the entire infinite series can fit on the open problem of whether or not one can pack a particular infinite series of rectangles into the unit square. Expand

Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes

- Mathematics, Computer Science
- Math. Oper. Res.
- 2006

It is shown that unlike the one-dimensional case, the two-dimensional packing problem cannot have an asymptotic polynomial time approximation scheme (APTAS), unless PNP, and the first approximation scheme for the problem of placing a collection of rectangles in a minimum-area encasing rectangle is obtained. Expand

#### References

SHOWING 1-10 OF 13 REFERENCES

A new algorithm for optimal bin packing

- Computer Science
- AAAI/IAAI
- 2002

This work presents a new algorithm for optimal bin packing, which appears to be asymptotically faster than the best existing optimal algorithm, and runs more that a thousand times faster on problems with 60 numbers. Expand

Rectangle-packing-based module placement

- Mathematics
- ICCAD 1995
- 1995

The first and the most critical stage in VLSI layout design is the placement, the background of which is the rectangle packing problem: Given many rectangular modules of arbitrary size, place them… Expand

Rectangle-packing-based module placement

- Proceedings of IEEE International Conference on Computer Aided Design (ICCAD)
- 1995

The first and the most critical stage in VLSI layout design is the placement, the background of which is the rectangle packing problem: Given many rectangular modules of arbitrary site, place them… Expand

Extending CHIP in order to solve complex scheduling and placement problems

- Mathematics, Computer Science
- JFPL
- 1992

In this paper, we show how the introduction of a new primitive constraint over finite domains in the constraint logic programming system CHIP allows us to find very good solutions for a large class… Expand

Lower bounds and reduction procedures for the bin packing problem

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1990

Lower bounds and a dominance criterion are presented and a reduction algorithm is derived and an experimental analysis is provided for both lower bounds and reduction algorithm. Expand

Branch-and-bound placement for building block layout

- Mathematics, Computer Science
- 28th ACM/IEEE Design Automation Conference
- 1991

A branch-and-bound placement technique for building block layout that effectively searches for an optimal placement in the whole solution space and decomposes the problem hierarchically and applies the method to each subproblem. Expand

Scheduling and Packing in the Constraint Language cc(FD)

- Mathematics
- 1992

Constraint logic programming (CLP), and its generalization in the cc framework, define a class of declarative constraint languages combining nondeterministic goal-directed programming with constraint… Expand

An O-tree representation of non-slicing floorplan and its applications

- Computer Science
- DAC '99
- 1999

A deterministic floorplanning algorithm utilizing the structure of O-tree is developed with promising performance with average 16% improvement in wire length, and 1% less in dead space over previous CPU-intensive cluster refinement method. Expand

Module placement on BSG-structure and IC layout applications

- Engineering
- ICCAD 1996
- 1996

A new method of packing the rectangles (modules) is presented with applications to IC layout design. It is based on the bounded-sliceline grid (BSG) structure. The BSG dissects the plane into rooms… Expand

Automatic Floorplan Design

- Mathematics
- DAC 1982
- 1982

The problem of allocating area to modules at the highest level of a top-down decomposition is treated in this paper. A theorem of Schoenberg is applied to obtain a good embedding of the module space… Expand