A SAT encoding for Multi-dimensional Packing Problems

Stéphane Grandcolas (1) , Cedric Pinto (1)

1 LSIS - Laboratoire des Sciences de l'Information et des Systèmes

The Orthogonal Packing Problem (OPP) consists in determining if a set of items can be packed into a given container. This decision problem is NP-complete. S. P. Fekete et al. modelled the problem in which the overlaps between the objects in each dimension are represented by interval graphs. In this paper we propose a SAT encoding of Fekete et al. characterization. Some results are presented, and the efficiency of this approach is compared with other SAT encodings.

Domains: Computer Science [cs]; Artificial Intelligence [cs.AI]

Stéphane Grandcolas, Cedric Pinto. A SAT encoding for Multi-dimensional Packing Problems. CPAIOR, Jun 2010, Bologna, Italy. ⟨hal-02471124⟩