Abstract: Finding the mathematically optimal way to pack rectangles into the smallest possible area is a classic NP-hard combinatorial optimization problem with significant implications for logistics, manufacturing, and chip design. This paper, presented at AAAI-10 by Eric Huang and Richard Korf, identifies that existing rectangle packing benchmarks are often too simple due to shared dimensions and symmetry. The authors propose two new, significantly harder benchmarks and introduce a new solver (HK10) featuring advanced variable ordering heuristics and balanced coordinate intervals. These improvements yield speedups of up to 500x over previous state-of-the-art solvers.
Introduction: The Complexity of Packing
The goal of rectangle packing is to find an enclosing rectangle (bounding box) of minimum area that can contain a set of given rectangles without any overlap. While conceptually similar to a game of Tetris, the search space for an optimal solution grows exponentially with the number of rectangles. Historically, the field has relied on the consecutive-square benchmark (packing squares of size $1 \times 1, 2 \times 2, \dots, N \times N$). However, the authors argue that these benchmarks are artificially easy because squares are highly symmetrical and large squares occupy most of the area, quickly narrowing the search space.
The Challenge of Non-Square Benchmarks
To better reflect real-world complexity, the authors introduced benchmarks where every rectangle has a unique dimension but shares the same perimeter. This prevents rectangles from "snapping" together perfectly based on shared side lengths, forcing the solver to manage irregular gaps and protrusions.
- Oriented Constant-Perimeter Benchmark: Rectangles of sizes $1 \times N, 2 \times (N-1), \dots, N \times 1$ with fixed orientation.
- Unoriented Constant-Perimeter Benchmark: Rectangles of sizes $1 \times (2N-1), 2 \times (2N-2), \dots, N \times N$ where rectangles can be rotated 90 degrees.
Search Strategy and Dominance
The authors' solver, HK10, splits the task into two parts: the containment problem (fitting rectangles into a specific box) and the minimal bounding box problem (finding the smallest such box). The core of their innovation lies in the containment search strategy.
Handling Dominance Conditions
In previous solvers, positions were pruned if they were "dominated"—meaning that placing a rectangle in a certain spot left a gap so small that no other remaining rectangle could ever fit there. While effective for squares, these conditions rarely triggered in the new, harder benchmarks. The authors updated the solver to detect when no positions are dominated and adjust interval assignments accordingly to maintain search efficiency.
Branching Factor and Balanced Intervals
Beyond dominance, the authors developed a Branching Factor Heuristic. Instead of simply picking the largest rectangle first, they calculate the number of possible choices at a search node and prioritize the variable that minimizes this branching factor. For oriented rectangles, they discovered that the most constrained variable is often the one with the greatest width, rather than the greatest area.
Additionally, they introduced Balanced Interval Sizes. Solvers typically divide x-coordinates into intervals to speed up the search. Previous methods used fixed-size intervals, often leading to lopsided search trees. By balancing these intervals, HK10 ensures that each branch of the search tree is equally constraining, preventing the solver from getting stuck in disproportionately difficult sub-problems.
Key Results and Performance Gains
The performance gains achieved by HK10 over the previous state-of-the-art (HK09) were dramatic:
- Oriented Benchmark: For $N=21$, the HK09 solver required nearly 4 days to find the optimal solution. The HK10 solver completed the same task in just 11 minutes and 20 seconds—a speedup of approximately 500x.
- Unoriented Benchmark: For $N=16$, the search time dropped from over 30 hours to roughly 1 hour.
- Benchmark Difficulty: The results confirmed that the new benchmarks are orders of magnitude harder than traditional ones. Solving $N=21$ for squares takes only 1 second, whereas the oriented constant-perimeter version takes over 11 minutes.
Conclusion
By identifying the limitations of symmetric benchmarks, Huang and Korf have pushed the boundaries of rectangle packing solvers. While the problem remains exponential and the unoriented benchmark continues to pose a significant challenge due to the doubled search space of rotation, the HK10 solver represents a major leap in handling the "messy" aspect ratios found in practical applications. Future work may involve more dynamic area constraints and integrated bounding box searches to further tame the complexity of optimal packing.
Summary updated