Un codage SAT pour les problèmes de placement

Résumé : Le problème de placement orthogonal (OPP) consiste à déterminer si un ensemble d'objets peut etre placé dans un conteneur de taille connue. Ce problème est NP-complet. Une modélisation de ce problème à base de graphes d'intervalles a été proposée par S. P. Fekete et al. Cette modélisation permet de représenter des classes de placements équivalents, diminuant d'autant l'espace de recherche. Dans cet article nous proposons de représenter par des formules de la logique propositionnelle la modélisation de S. P. Fekete et al. Nous avons implémenté cette approche en utilisant le solveur MiniSat, et nous l'avons comparée d'une part avec les résultats de S. P. Fekete et al. sur des problèmes classiques, et d'autre part avec l'approche de T. Soh et al. basée aussi sur un codage SAT sur des problèmes de Strip Packing.
Type de document :
Communication dans un congrès
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.149-156, 2010
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00520285
Contributeur : Christophe Lecoutre <>
Soumis le : mercredi 22 septembre 2010 - 18:33:24
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 11:21:08

Fichier

pinto.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : inria-00520285, version 1

Collections

Citation

Stéphane Grandcolas, Cedric Pinto. Un codage SAT pour les problèmes de placement. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.149-156, 2010. 〈inria-00520285〉

Partager

Métriques

Consultations de la notice

113

Téléchargements de fichiers

233