Which rectangle sets have perfect packings?

Operations Research Perspectives

Florian Braam¹  Daan van den Berg² 

[1] Energy Global Advies B.V., Rotterdam, The Netherlands;Yamasan Science&Education, Amsterdam, The Netherlands;

关键词: Problem structuring;    Perfect rectangle packing;    Solvability;    Phase transition;    NP-complete;   

DOI  :  

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown