Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

https://hal.inria.fr/inria-00085816
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 4:07:21 PM
Last modification on : Wednesday, June 24, 2020 - 4:18:09 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:10:16 AM

File

Identifiers

  • 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. ⟨inria-00085816⟩

Share

Metrics

Record views

431

Files downloads

542