TR2004-059

Exhaustive Approaches to 2D Rectangular Perfect Packings

    •  N. Lesh, J. Marks, A. McMahon, M. Mitzenmacher, "Exhaustive Approaches to 2D Rectangular Perfect Packings", Tech. Rep. TR2004-059, Mitsubishi Electric Research Laboratories, Cambridge, MA, April 2004.
      BibTeX TR2004-059 PDF
      • @techreport{MERL_TR2004-059,
      • author = {N. Lesh, J. Marks, A. McMahon, M. Mitzenmacher},
      • title = {Exhaustive Approaches to 2D Rectangular Perfect Packings},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR2004-059},
      • month = apr,
      • year = 2004,
      • url = {https://www.merl.com/publications/TR2004-059/}
      • }
Abstract:

In this paper, we consider the two-dimensional rectangular strip packing problem, in the case wahere there is a perfect packing; that is, there is no wasted space. One can think of the problem as a jigsaw puzzle with oriented rectangular pieces. Although this comprises a quite special case for strip packing, we have found it useful as a subroutine in related work. We domonstrate a simple pruning approach that makes a brand-and-bound-based exhaustive search extemely effective for problems with less than 30 rectangles.