Optimal rectangle packing: a meta-CSP approach

摘要: We present a new approach to optimal rectangle packing, an NP-complete problem that can be used model many simple scheduling tasks. Recent attempts at incorporating artificial intelligence search techniques the of packing have focused on CSP formulation, in which partial assignments are defined fixed placement subset rectangles. Our technique takes significant departure from this space, as we instead view subsets relative pairwise relationships between This recalls meta-CSP commonly constructed constraint-based temporal reasoning, and is thus candidate for several pruning been developed field. apply these domain develop suite exploit both symmetry geometry particular domain. then provide experimental results demonstrating our performs competitively compared previous state-of-the-art series benchmarks, matching or surpassing it speed nearly all instances. Finally, conjecture particularly appropriate problems containing large rectangles, difficult fixed-placement formulation handle efficiently.