[JFRO] Journee "Optimisation convexe" le
Forum 'Annonces' - Sujet créé le 2004-06-06
Bonjour,
La dixieme journee thematique des "Journees Franciliennes de Recherche Operationnelle" (JFRO) se tiendra le :
Vendredi 11 Juin 2004
au Carre des Sciences
Ministere de l'Education Nationale, de la Recherche et de la Technologie
1, rue Descartes 75005 Paris
Entree par le 25, rue de la Montagne Sainte Genevieve
(Metro Maubert-Mutualite ou Metro Cardinal Lemoine).
sur le theme :
"Optimisation convexe: relaxation lagrangienne,
decomposition et generation de colonnes"
Vous pouvez vous inscrire simplement en repondant a ce mail ou bien via le site JFRO a l'URL
http://www.roadef.org
rubrique: Groupes de travail
lien: JFRO: Journees Franciliennes de Recherche Operationnelle
Attention: Pour cause de plan Vigipirate Renforce, le Carre des Sciences nous demande de lui faire parvenir la liste des inscrits au moins 48h a l'avance, la date limite d'inscription est donc fixee au mardi 8 juin 2004.
Vous trouverez sur le site un programme detaille de la
journee dont voici un resume :
------------------------------------------------------------
Programme previsionnel de la journee
-------------------------------------------------------------
9H30 - 10H Accueil des participants
10H - 12H Claude Lemarechal - INRIA
DUALITE POUR TOUS: THEORIE ET ALGORITHMES DE BASE
12h00 - 13h50 DEJEUNER
13h50 - 14h30 Jean-Philippe Vial - Universite de Geneve
RESOLUTION DE PROBLEMES DE MULTIFLOTS LINEAIRES PAR RELAXATION LAGRANGIENNE PARTIELLE
14h30-15h10 Nancy Perrot - Universite de Bordeaux
COMPARAISON DE LA METHODE DES FAISCEAUX ET
DE LA GENERATION DE COLONNES CLASSIQUE
15h10 - 15h30 PAUSE
15h30-16h10 Monique Guignard-Spielberg - Departement de OPIM, Wharton School, Universite de Pennsylvanie, Philadelphie
CAS PARTICULIERS DE LA RELAXATION LAGRANGIENNE
16h10-16h50 Thierry Benoist - Bouygues SA
BORNES SUPERIEURES POUR LE TV-BREAKS PACKING PROBLEM
-------------------------------------------------------------
La participation a cette journee est gratuite et ouverte a tous.
Toute information concernant cette journee ou les precedentes
sont disponibles sur le site JFRO a l'URL
http://www.roadef.org
rubrique: Groupes de travail
lien: JFRO: Journees Franciliennes de Recherche Operationnelle
Le comite d'organisation :
- Laurent Alfandari (Essec)
- Eric Angel (Universite d'Evry)
- Lucas Letocart (Universite Paris 13)
- Cecile Murat (Universite Paris Dauphine)
----------------------------------------------------------------------
DUALITE POUR TOUS: THEORIE ET ALGORITHMES DE BASE
Claude Lemarechal - INRIA
Resume
Bien plus qu'un outil algorithmique, la relaxation lagrangienne
est en fait une methodologie generale, quasi incontournable des
qu'il s'agit de convexifier un probleme d'optimisation.
C'est dans cette optique qu'elle sera presentee, en tant que
realisation pratique d'une theorie assez abstraite: la dualite.
On en degagera les principes generaux dans un langage aussi clair
que possible, en insistant sur son etroite relation avec d'autres
relaxations a priori differentes (SDP) et la generation de colonnes.
Du point de vue numerique, on presentera et on discutera les algorithmes
bien connus (sous-gradient et ellipsoide, Dantzig-Wolfe) mais aussi les
plus recents (faisceaux et accpm), qui sont en fait des versions
stabilisees de la generation de colonnes traditionnelle.
Une reference parmi d'autres: C. Lemarechal: "The omnipresence of
Lagrange", 4OR 1 (2003) 7-25
RESOLUTION DE PROBLEMES DE MULTIFLOTS LINEAIRES PAR
RELAXATION LAGRANGIENNE PARTIELLE
Jean-Philippe Vial - Universite de Geneve,
travail joint avec F. Babonneau (Universite de Geneve)
et O. du Merle (Air France)
Resume
L'experience montre que dans la plupart des problemes de multiflots
lineaires, peu d'arcs sont satures a l'optimum. Nous exploitons cette
propriete pour definir une relaxation lagrangienne partielle et un
probleme dual reduit. L'ensemble des arcs non satures est estime
dynamiquement par une strategie d'ensemble actif. Le dual lagrangien est
resolu par une methode de centres analytiques. La methode fournit une
paire primale-duale de solutions realisables et donc une mesure de
precision de la solution.
L'algorithme est utilise pour resoudre les problemes planar et grid de la
litterature, ainsi que les problemes de trafic Barcelone, Winnipeg,
Philadlephie et Chicago. Certains de ces problemes sont de dimension
considerable (jusqu'a 14.000 noeuds, 40.000 arcs et 2.000.000 de
commodites).
On trouve des solutions optimales a 5 chiffres significatifs pour les
problemes des collections planar et grid (sauf le planar 2500) et des
solutions primales realisables pour tous les autres.
COMPARAISON DE LA METHODE DES FAISCEAUX ET DE LA GENERATION DE COLONNES
CLASSIQUE
Nancy Perrot - Universite de Bordeaux
Resume
Quand on utilise une approche de generation de colonnes pour resoudre un
probleme
decomposable mixte en nombres entiers, il est usuel de resoudre
le probleme maitre par la programmation lineaire generalisee.
Dans l'espace dual cette methode est connue sous le nom d'algorithme de
plans coupants de Kelley. Cependant, il existe des methodes alternatives
plus stables, avec des convergences theoriques meilleures, comme la
methode des faisceaux, qui peuvent etre utilisees a la place de
l'algorithme standard de Kelley.
Nous presenterons les resultats preliminaires de tests comparatifs entre
la methode des faisceaux et l'algorithme de Kelley, ces tests ont ete
effectues sur des applications variees (probleme de decoupe, probleme de
production par lots, probleme de voyageur de commerce, probleme de
tournees).
CAS PARTICULIERS DE LA RELAXATION LAGRANGIENNE
Monique Guignard-Spielberg - Departement de OPIM, Wharton School,
Universite de Pennsylvanie, Philadelphie
Resume
Apres un bref rappel de l'interpretation geometrique de la relaxation
lagrangienne, des consequences de la propriete d'integralite, de la
generation de plans secants et de colonnes, et de la decomposition et la
substitution lagrangienne, nous presenterons quelques cas particuliers.
Considerons les trois questions suivantes :
(1) est-il possible d'obtenir une borne "forte" (c.a.d. une borne
meilleure que la borne par programmation lineaire) bien que les
sous-problemes lagrangiens soient faciles a resoudre ?
(2) est-il possible d'utiliser le fait qu'un probleme lagrangien est
decomposable pour decomposer le probleme des plants secants?
(3) si la decomposition lagrangienne (DL) est meilleure que les deux
relaxations lagrangiennes associees, est-il quand meme possible d'obtenir
une borne aussi forte que la borne DL par relaxation de copies agregees
plutot que de copies exactes des variables?
Nous presenterons des exemples montrant que la reponse est oui dans les
trois cas.
BORNES SUPERIEURES POUR LE TV-BREAKS PACKING PROBLEM
Thierry Benoist - Bouygues SA
Resume
Au lieu de vendre les spots publicitaires un par un, certaines chaines
satellites francaises ont decide en 2002 de modifier leur offre
commerciale de facon a vendre des packages de spots. Ces nouvelles
Conditions Géîérales de Vente conduisent a un interessant probleme
d'optimisation que nous nommons TV-Breaks Packing (TVBP).
Des algorithmes efficaces de resolution de ce probleme ont ete obtenus
par hybridation de programmation par contraintes et de recherche locale.
Dans cette presentation nous nous interessons au calcul de bornes
superieures du nombre de packages, en dualisant les contraintes de
capacites sur les ecrans.
Cette borne lagrangienne est amelioree par la prise en compte de regrets
minimaux et finalement encapsulee dans un Branch and Bound limite. Ces
bornes etablissent l'optimalite de plusieurs des meilleures solutions
connues.
La dixieme journee thematique des "Journees Franciliennes de Recherche Operationnelle" (JFRO) se tiendra le :
Vendredi 11 Juin 2004
au Carre des Sciences
Ministere de l'Education Nationale, de la Recherche et de la Technologie
1, rue Descartes 75005 Paris
Entree par le 25, rue de la Montagne Sainte Genevieve
(Metro Maubert-Mutualite ou Metro Cardinal Lemoine).
sur le theme :
"Optimisation convexe: relaxation lagrangienne,
decomposition et generation de colonnes"
Vous pouvez vous inscrire simplement en repondant a ce mail ou bien via le site JFRO a l'URL
http://www.roadef.org
rubrique: Groupes de travail
lien: JFRO: Journees Franciliennes de Recherche Operationnelle
Attention: Pour cause de plan Vigipirate Renforce, le Carre des Sciences nous demande de lui faire parvenir la liste des inscrits au moins 48h a l'avance, la date limite d'inscription est donc fixee au mardi 8 juin 2004.
Vous trouverez sur le site un programme detaille de la
journee dont voici un resume :
------------------------------------------------------------
Programme previsionnel de la journee
-------------------------------------------------------------
9H30 - 10H Accueil des participants
10H - 12H Claude Lemarechal - INRIA
DUALITE POUR TOUS: THEORIE ET ALGORITHMES DE BASE
12h00 - 13h50 DEJEUNER
13h50 - 14h30 Jean-Philippe Vial - Universite de Geneve
RESOLUTION DE PROBLEMES DE MULTIFLOTS LINEAIRES PAR RELAXATION LAGRANGIENNE PARTIELLE
14h30-15h10 Nancy Perrot - Universite de Bordeaux
COMPARAISON DE LA METHODE DES FAISCEAUX ET
DE LA GENERATION DE COLONNES CLASSIQUE
15h10 - 15h30 PAUSE
15h30-16h10 Monique Guignard-Spielberg - Departement de OPIM, Wharton School, Universite de Pennsylvanie, Philadelphie
CAS PARTICULIERS DE LA RELAXATION LAGRANGIENNE
16h10-16h50 Thierry Benoist - Bouygues SA
BORNES SUPERIEURES POUR LE TV-BREAKS PACKING PROBLEM
-------------------------------------------------------------
La participation a cette journee est gratuite et ouverte a tous.
Toute information concernant cette journee ou les precedentes
sont disponibles sur le site JFRO a l'URL
http://www.roadef.org
rubrique: Groupes de travail
lien: JFRO: Journees Franciliennes de Recherche Operationnelle
Le comite d'organisation :
- Laurent Alfandari (Essec)
- Eric Angel (Universite d'Evry)
- Lucas Letocart (Universite Paris 13)
- Cecile Murat (Universite Paris Dauphine)
----------------------------------------------------------------------
DUALITE POUR TOUS: THEORIE ET ALGORITHMES DE BASE
Claude Lemarechal - INRIA
Resume
Bien plus qu'un outil algorithmique, la relaxation lagrangienne
est en fait une methodologie generale, quasi incontournable des
qu'il s'agit de convexifier un probleme d'optimisation.
C'est dans cette optique qu'elle sera presentee, en tant que
realisation pratique d'une theorie assez abstraite: la dualite.
On en degagera les principes generaux dans un langage aussi clair
que possible, en insistant sur son etroite relation avec d'autres
relaxations a priori differentes (SDP) et la generation de colonnes.
Du point de vue numerique, on presentera et on discutera les algorithmes
bien connus (sous-gradient et ellipsoide, Dantzig-Wolfe) mais aussi les
plus recents (faisceaux et accpm), qui sont en fait des versions
stabilisees de la generation de colonnes traditionnelle.
Une reference parmi d'autres: C. Lemarechal: "The omnipresence of
Lagrange", 4OR 1 (2003) 7-25
RESOLUTION DE PROBLEMES DE MULTIFLOTS LINEAIRES PAR
RELAXATION LAGRANGIENNE PARTIELLE
Jean-Philippe Vial - Universite de Geneve,
travail joint avec F. Babonneau (Universite de Geneve)
et O. du Merle (Air France)
Resume
L'experience montre que dans la plupart des problemes de multiflots
lineaires, peu d'arcs sont satures a l'optimum. Nous exploitons cette
propriete pour definir une relaxation lagrangienne partielle et un
probleme dual reduit. L'ensemble des arcs non satures est estime
dynamiquement par une strategie d'ensemble actif. Le dual lagrangien est
resolu par une methode de centres analytiques. La methode fournit une
paire primale-duale de solutions realisables et donc une mesure de
precision de la solution.
L'algorithme est utilise pour resoudre les problemes planar et grid de la
litterature, ainsi que les problemes de trafic Barcelone, Winnipeg,
Philadlephie et Chicago. Certains de ces problemes sont de dimension
considerable (jusqu'a 14.000 noeuds, 40.000 arcs et 2.000.000 de
commodites).
On trouve des solutions optimales a 5 chiffres significatifs pour les
problemes des collections planar et grid (sauf le planar 2500) et des
solutions primales realisables pour tous les autres.
COMPARAISON DE LA METHODE DES FAISCEAUX ET DE LA GENERATION DE COLONNES
CLASSIQUE
Nancy Perrot - Universite de Bordeaux
Resume
Quand on utilise une approche de generation de colonnes pour resoudre un
probleme
decomposable mixte en nombres entiers, il est usuel de resoudre
le probleme maitre par la programmation lineaire generalisee.
Dans l'espace dual cette methode est connue sous le nom d'algorithme de
plans coupants de Kelley. Cependant, il existe des methodes alternatives
plus stables, avec des convergences theoriques meilleures, comme la
methode des faisceaux, qui peuvent etre utilisees a la place de
l'algorithme standard de Kelley.
Nous presenterons les resultats preliminaires de tests comparatifs entre
la methode des faisceaux et l'algorithme de Kelley, ces tests ont ete
effectues sur des applications variees (probleme de decoupe, probleme de
production par lots, probleme de voyageur de commerce, probleme de
tournees).
CAS PARTICULIERS DE LA RELAXATION LAGRANGIENNE
Monique Guignard-Spielberg - Departement de OPIM, Wharton School,
Universite de Pennsylvanie, Philadelphie
Resume
Apres un bref rappel de l'interpretation geometrique de la relaxation
lagrangienne, des consequences de la propriete d'integralite, de la
generation de plans secants et de colonnes, et de la decomposition et la
substitution lagrangienne, nous presenterons quelques cas particuliers.
Considerons les trois questions suivantes :
(1) est-il possible d'obtenir une borne "forte" (c.a.d. une borne
meilleure que la borne par programmation lineaire) bien que les
sous-problemes lagrangiens soient faciles a resoudre ?
(2) est-il possible d'utiliser le fait qu'un probleme lagrangien est
decomposable pour decomposer le probleme des plants secants?
(3) si la decomposition lagrangienne (DL) est meilleure que les deux
relaxations lagrangiennes associees, est-il quand meme possible d'obtenir
une borne aussi forte que la borne DL par relaxation de copies agregees
plutot que de copies exactes des variables?
Nous presenterons des exemples montrant que la reponse est oui dans les
trois cas.
BORNES SUPERIEURES POUR LE TV-BREAKS PACKING PROBLEM
Thierry Benoist - Bouygues SA
Resume
Au lieu de vendre les spots publicitaires un par un, certaines chaines
satellites francaises ont decide en 2002 de modifier leur offre
commerciale de facon a vendre des packages de spots. Ces nouvelles
Conditions Géîérales de Vente conduisent a un interessant probleme
d'optimisation que nous nommons TV-Breaks Packing (TVBP).
Des algorithmes efficaces de resolution de ce probleme ont ete obtenus
par hybridation de programmation par contraintes et de recherche locale.
Dans cette presentation nous nous interessons au calcul de bornes
superieures du nombre de packages, en dualisant les contraintes de
capacites sur les ecrans.
Cette borne lagrangienne est amelioree par la prise en compte de regrets
minimaux et finalement encapsulee dans un Branch and Bound limite. Ces
bornes etablissent l'optimalite de plusieurs des meilleures solutions
connues.