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

Julien Dupuis 1 Pierre Schaus 2 Yves Deville 1
1 3MI-ENSMSE - Département Méthodes et Modèles Mathématiques pour l'Industrie
2 Dynadec - Dynadec
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.
Type de document :
Communication dans un congrès
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.133-138, 2010
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00520301
Contributeur : Christophe Lecoutre <>
Soumis le : mercredi 22 septembre 2010 - 18:57:29
Dernière modification le : mercredi 29 novembre 2017 - 10:07:25
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 11:21:35

Fichier

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

Identifiants

  • HAL Id : inria-00520301, version 1

Collections

JFPC2010

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, 2010. 〈inria-00520301〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

159

Contact


archive-ouverte@inria.fr