Dupuis, Julien
[UCL]
Schaus, Pierre
[UCL]
Deville, Yves
[UCL]
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.
Bibliographic reference |
Dupuis, Julien ; Schaus, Pierre ; Deville, Yves. Vérification de consistence pour la constrainte de bin packing.Sixièmes journées Francophones de programmation par contraintes (JFPC 2010) (Caen, France, du 09/06/2010 au 11/06/2010). |
Permanent URL |
http://hdl.handle.net/2078.1/86173 |