Which rectangle sets have perfect packings?

Florian Braam and Daan van den Berg

Operations Research Perspectives, 2022, vol. 9, issue C

Abstract: In the perfect rectangle packing problem, a set of rectangular items have to be placed inside a rectangular container without overlap or empty space. In this paper, we generate a large number of random instances and decide them all with an exact solving algorithm. Both an instance’s solution probability and its hardness measured in recursions or system time, seems to critically depend on tmax, a parameter in the generation procedure that assigns the maximally choosable random side lengths of items in the instance. We numerically characterize the solvability across instance sizes, and derive a rule for generating (un)solvable problem instances of arbitrary size.

Keywords: Problem structuring; Perfect rectangle packing; Solvability; Phase transition; NP-complete (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S2214716021000270
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:oprepe:v:9:y:2022:i:c:s2214716021000270

DOI: 10.1016/j.orp.2021.100211

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().