Propagation de coûts réduits et énumération implicite pour le problème du sac à dos multidimensionnel en 0-1

Résumé : Dans de précédents travaux, nous avons proposé une heuristique de xation de variables pour le probl ème du sac à dos multidimensionnel en variables binaires (01MDK). Cette approche tient compte des coordonn ées des optima fractionnaires calculés dans des hyperplans contenant l'optimum binaire. Ce premier algorithme a obtenu les meilleurs minorants sur les instances de P.C Chu et J.E Beasley qui font partie de la OR-Library. Bien qu'intéressante du point de vue qualitatif, cette méthode ne prouve pas l'optimalité des solutions qu'elle trouve et peut xer des variables à une valeur non optimale. Nous proposons ici une méthode d'énumération implicite basée sur une analyse des coûts réduits, qui tend à xer exactement les variables hors base. La prise en compte d'une contrainte de distance au gap, par propagation des coûts réduits, ainsi qu'une mé- thode efficace de branchements nous permettent d'élaguer signicativement l'arbre de recherche. Du point de vue expérimental, ces travaux apportent deux contributions principales : (1) l'obtention de plusieurs nouvelles preuves d'optimalité pour des instances difficiles de la OR-Library et (2) la réduction de certaines instances pour lesquelles l'algorithme n'a pas trouvé la solution optimale.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00085816
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 16:07:21
Dernière modification le : vendredi 9 février 2018 - 16:58:07
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:10:16

Fichier

Identifiants

  • HAL Id : inria-00085816, version 1

Collections

Citation

Sylvain Boussier, Yannick Vimont, Michel Vasquez. Propagation de coûts réduits et énumération implicite pour le problème du sac à dos multidimensionnel en 0-1. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085816〉

Partager

Métriques

Consultations de la notice

405

Téléchargements de fichiers

416