Abstract : 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.
https://hal-amu.archives-ouvertes.fr/hal-02471124 Contributor : Stéphane GrandcolasConnect in order to contact the contributor Submitted on : Friday, February 7, 2020 - 5:41:18 PM Last modification on : Saturday, June 25, 2022 - 7:49:36 PM Long-term archiving on: : Friday, May 8, 2020 - 4:47:33 PM