Propagation de coûts réduits et énumération implicite pour le problème du sac à dos multidimensionnel en 0-1 - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

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.
Fichier principal
Vignette du fichier
53.pdf (283.21 Ko) Télécharger le fichier

Dates et versions

inria-00085816 , version 1 (14-07-2006)

Identifiants

  • HAL Id : inria-00085816 , version 1

Citer

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⟩
190 Consultations
473 Téléchargements

Partager

Gmail Facebook X LinkedIn More