Optimal Rectangle Packing on Non-Square Benchmarks

Authors

  • Eric Huang UCLA
  • Richard Korf UCLA

DOI:

https://doi.org/10.1609/aaai.v24i1.7538

Keywords:

search, constraint satisfaction, scheduling, rectangle packing

Abstract

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 two new benchmarks, one where the orientation of the rectangles is fixed and one where it is free, that include rectangles of various aspect ratios. The new benchmarks avoid certain properties of easy instances, which we identify as instances where rectangles have dimensions in common or where a few rectangles occupy most of the area. Our benchmarks are much more difficult for the previous state-of-the-art solver, requiring orders of magnitude more time, compared to similar-sized instances from a popular benchmark consisting only of squares. On the new benchmarks, we improve upon the previous strategy used to handle dominance conditions, we define a variable order over non-square rectangles that generalizes previous strategies, and we present a way to adjust the sizes of intervals of values for each rectangle's x-coordinates. Using these techniques together, we can solve the new oriented benchmark about 500 times faster, and the new unoriented benchmark about 40 times faster than the previous state-of-the-art.

Downloads

Published

2010-07-03

How to Cite

Huang, E., & Korf, R. (2010). Optimal Rectangle Packing on Non-Square Benchmarks. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 83-88. https://doi.org/10.1609/aaai.v24i1.7538

Issue

Section

Constraints, Satisfiability, and Search