Bien plus qu'un outil algorithmique, la relaxation lagrangienne est en fait une méthodologie générale, quasi incontournable dès qu'il s'agit de convexifier un problème d'optimisation. C'est dans cette optique qu'elle sera présentée, en tant que réalisation pratique d'une théorie assez abstraite: la dualité.

On en dégagera les principes généraux dans un langage aussi clair que possible, en insistant sur son étroite relation avec d'autres relaxations a priori différentes (SDP) et la génération de colonnes. Du point de vue numérique, on présentera et on discutera les algorithmes bien connus (sous-gradient et ellipsoide, Dantzig-Wolfe) mais aussi les plus récents (faisceaux et accpm), qui sont en fait des versions stabilisées de la génération de colonnes traditionnelle.

Une reference parmi d'autres: C. Lemaréchal: "The omnipresence of Lagrange", 4OR 1 (2003) 7-25

L'expérience montre que dans la plupart des problèmes de multiflots linéaires, peu d'arcs sont saturés à l'optimum. Nous exploitons cette propriété pour définir une relaxation lagrangienne partielle et un problème dual réduit. L'ensemble des arcs non saturés est estimé dynamiquement par une stratégie d'ensemble actif. Le dual lagrangien est résolu par une méthode de centres analytiques. La méthode fournit une paire primale-duale de solutions réalisables et donc une mesure de précision de la solution.

L'algorithme est utilisé pour résoudre les problèmes planar et grid de la littérature, ainsi que les problèmes de trafic Barcelone, Winnipeg, Philadlephie et Chicago. Certains de ces problèmes sont de dimension considérable (jusqu'à 14.000 noeuds, 40.000 arcs et 2.000.000 de commodités). On trouve des solutions optimales à 5 chiffres significatifs pour les problèmes des collections planar et grid (sauf le planar 2500) et des solutions primales réalisables pour tous les autres.

Quand on utilise une approche de génération de colonnes pour résoudre un problème décomposable mixte en nombres entiers, il est usuel de résoudre le problème maitre par la programmation linéaire généralisée.

Dans l'espace dual cette mèthode est connue sous le nom d'algorithme de plans coupants de Kelley. Cependant, il existe des méthodes alternatives plus stables, avec des convergences théoriques meilleures, comme la méthode des faisceaux, qui peuvent etre utilisées à la place de l'algorithme standard de Kelley. Nous présenterons les résultats préliminaires de tests comparatifs entre la méthode des faisceaux et l'algorithme de Kelley, ces tests ont été effectués sur des applications variées (problème de découpe, problème de production par lots, problème de voyageur de commerce, problème de tournées).

Apres un bref rappel de l'interprétation géométrique de la relaxation lagrangienne, des conséquences de la propriété d'intégralité, de la génération de plans sécants et de colonnes, et de la décomposition et la substitution lagrangienne, nous présenterons quelques cas particuliers.

Considérons les trois questions suivantes :
(1) est-il possible d'obtenir une borne « forte» (c.à.d. une borne meilleure que la borne par programmation linéaire) bien que les sous-problèmes lagrangiens soient faciles à résoudre ?
(2) est-il possible d'utiliser le fait qu'un problème lagrangien est décomposable pour décomposer le problème des plants sécants?
(3) si la décomposition lagrangienne (DL) est meilleure que les deux relaxations lagrangiennes associées, est-il quand meme possible d'obtenir une borne aussi forte que la borne DL par relaxation de copies agrégées plutot que de copies exactes des variables?
Nous présenterons des exemples montrant que la réponse est oui dans les trois cas.

Au lieu de vendre les spots publicitaires un par un, certaines chaines satellites francaises ont décidé en 2002 de modifier leur offre commerciale de facon à vendre des packages de spots. Ces nouvelles Conditions Générales de Vente conduisent à un intéressant problème d'optimisation que nous nommons TV-Breaks Packing (TVBP). Des algorithmes efficaces de résolution de ce problème ont été obtenus par hybridation de programmation par contraintes et de recherche locale. Dans cette présentation nous nous intéressons au calcul de bornes supérieures du nombre de packages, en dualisant les contraintes de capacités sur les écrans. Cette borne lagrangienne est améliorée par la prise en compte de regrets minimaux et finalement encapsulée dans un Branch and Bound limité. Ces bornes établissent l'optimalité de plusieurs des meilleures solutions connues.