La ROADEF
La R.O.A.D
Evénements
Prix
Publications
Plus
Forums
Connexion
Livre blanc

[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.