Groupe d’études et de recherche en analyse des décisions

Le sac à dos avec réoptimisation pour la résolution du dual Lagrangien du biknapsack en variables 0-1

Gérard Plateau Laboratoire d'Informatique de Paris-Nord (LIPN), France

On envisage la relaxation Lagrangienne du sac à dos à deux contraintes en 0-1, par dualisation de l'une de ses deux contraintes. Une méthode de sous-gradients dédiée à la résolution du dual Lagrangien associé nécessite la résolution d'une suite de problèmes de sac à dos 0-1 avec contrainte invariante mais dont l'objectif évolue avec la suite des multiplicateurs de Lagrange engendrés.

Une accélération de la méthode de sous-gradients est obtenue lorsque des techniques de réoptimisation sont envisagées pour les problèmes de sac à dos de fin de procédure (des multiplicateurs très proches engendrent des sacs à dos très voisins).

La méthode BPK pour la résolution exacte du sac à dos 0-1 est rappelée : prétraitement de complexité linéaire (résolution en continu, heuristique gloutonne, fixation de variables via la relaxation lagrangienne) suivi d'une phase d'énumération qui fait coopérer le branch-and-bound et la programmation dynamique).

L'heuristique Lagrangienne MARIE (Method combining Approximation and Reoptimization for Integer programming Evoluating instances) pour le biknapsack 0-1 est ensuite présentée : elle intègre la notion de réoptimisation mais aussi une recherche locale et une fixation de variables du problème global. Cette méthode MARIE a été testée sur un échantillon de vingt instances de biknapsack à 1000 variables 0-1, dont les données corrélées sont générées aléatoirement. Elle permet d'obtenir des écarts de dualité presque nuls en de faibles temps de calcul (temps moyen inférieur à 2,4 secondes sur une station SUN Ultra 5).