Skip to Main content Skip to Navigation
Conference papers

Vérification de consistance pour la contrainte de bin packing revisitée

Résumé : La contrainte Pack de bin packing introduite par P. Shaw [Shaw, 2004] utilise un algorithme de détection d'inconsistance. Ce test est basé sur une réduction de la solution partielle à un problème de bin packing standard, et sur le calcul d'une borne inférieure sur le nombre de boîtes dans le problème réduit. Nous proposons deux nouveaux algorithmes de réduction et prouvons que l'un d'eux domine théoriquement les autres. Les résultats expérimentaux montrent qu'une combinaison de nos deux réductions améliore la qualité du filtre.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00520301
Contributor : Christophe Lecoutre Connect in order to contact the contributor
Submitted on : Wednesday, September 22, 2010 - 6:57:29 PM
Last modification on : Wednesday, June 24, 2020 - 4:18:18 PM
Long-term archiving on: : Thursday, October 25, 2012 - 11:21:35 AM

File

dupuis.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : inria-00520301, version 1

Collections

Citation

Julien Dupuis, Pierre Schaus, yves Deville. Vérification de consistance pour la contrainte de bin packing revisitée. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.133-138. ⟨inria-00520301⟩

Share

Metrics

Record views

43

Files downloads

103