Homepage
Previous JFRO
Organizing committee
Contact
10th Ile-de-France Operation Research Day
Optimisation convexe: relaxation lagrangienne, décomposition et génération de colonnes
Date
This day took place
Friday, the 11 June 2004
Place
Carré des Sciences Amphithéatre Yves Stourdze Ministère de l'Education Nationale, de la Recherche et de la Technologie 1, rue Descartes - 75005 Paris

Program of the day


09h30-10h00
Accueil des participants

10h00-12h00
Dualité pour tous : Théorie et algorithmes de base
Abstract : 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

12h00-13h50
Déjeuner

13h50-14h30
Résolution de problèmes de multiflots linéaires par relaxation lagrangienne partielle
Jean-Philippe Vial (Université de Genève), F Babonneau (Université de Genève) and O du Merle (Air France)
Abstract : 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.

14h30-15h10
Comparaison de la méthode des faisceaux et de la génération de colonne classique
Nancy Perrot (Université de Bordeaux)
Abstract : 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).

15h10-15h30
Pause

15h30-16h10
Cas particuliers de la relaxation lagrangienne
Monique Guignard-Spielberg (Département de OPIM, Wharton School, Université de Pennsylvanie, Philadelphie)
Abstract : 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.

16h10-16h50
Bornes supérieures pour le tv-breaks packing problem
Thierry Benoist (Bouygues SA)
Abstract : 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.

Choose language : Français English