Skip to Main content Skip to Navigation
Conference papers

A SAT encoding for Multi-dimensional Packing Problems

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-02471124
Contributor : Stéphane Grandcolas <>
Submitted on : Friday, February 7, 2020 - 5:41:18 PM
Last modification on : Monday, March 30, 2020 - 8:41:48 AM
Long-term archiving on: : Friday, May 8, 2020 - 4:47:33 PM

File

CPAIOR2010-finale.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02471124, version 1

Citation

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

Share

Metrics

Record views

38

Files downloads

114