soutenance de th
Forum 'Annonces' - Sujet créé le 2004-11-04
Coralie Triadou
Thèse Cifre Cermsem (université Paris 1) / Artelys
soutenue le 24 Septembre 2004
Méthodes de faisceaux et de relaxation lagrangienne pour le traitement de grands problèmes d'optimisation combinatoire.
Composition du jury :
Jean-Marc BONNISSEAU Président du jury
Claude LEMARÉCHAL Directeur de thèse
Cuong LE VAN Examinateur
Philippe MAHEY Rapporteur
Arnaud RENAUD Examinateur
Jean-Philippe VIAL Rapporteur
Résumé de la thèse :
Le but de ce travail de thèse est de réaliser et valider un logiciel
d'optimisation non-différentiable performant qui puisse traiter des
relaxations lagrangiennes de grands problèmes combinatoires. Le travail
réalisé s'est organisé autour de trois axes : mise en oeuvre d'une méthode
de faisceaux, études numériques de cette méthode et application à un
problème combinatoire difficile. La première partie décrit la méthode de
faisceaux réalisée. La résolution du problème quadratique est détaillée,
dans le cas d'un problème non contraint et dans le cas d'un problème avec
contraintes de bornes. Le traitement de contraintes convexes et
d'objectifs désagrégés dans le programme quadratique sont évoqués. Les
études numériques réalisées ont permis de mettre en évidence un choix de
paramètres robuste et de préciser la validité de deux critères d'arrêt.
La troisième partie concerne un problème de dimensionnement de réseau de
télécommunications. L'objectif est de minimiser des coûts d'investissements
sur plusieurs années successives. Le réseau obtenu à chaque période
successive doit permettre de faire transiter toutes les demandes de trafic.
Différentes approches pour le choix des investissements ont été comparées
sur des réseaux de dix à quinze villes. On part d'une modélisation par
Programmation Linéaire en Nombres Entiers et on propose plusieurs
techniques de décomposition,
dont une relaxation lagrangienne. Une approche par réseau cible a permis
d'obtenir des solutions réalisables en un temps raisonnable.
Thèse Cifre Cermsem (université Paris 1) / Artelys
soutenue le 24 Septembre 2004
Méthodes de faisceaux et de relaxation lagrangienne pour le traitement de grands problèmes d'optimisation combinatoire.
Composition du jury :
Jean-Marc BONNISSEAU Président du jury
Claude LEMARÉCHAL Directeur de thèse
Cuong LE VAN Examinateur
Philippe MAHEY Rapporteur
Arnaud RENAUD Examinateur
Jean-Philippe VIAL Rapporteur
Résumé de la thèse :
Le but de ce travail de thèse est de réaliser et valider un logiciel
d'optimisation non-différentiable performant qui puisse traiter des
relaxations lagrangiennes de grands problèmes combinatoires. Le travail
réalisé s'est organisé autour de trois axes : mise en oeuvre d'une méthode
de faisceaux, études numériques de cette méthode et application à un
problème combinatoire difficile. La première partie décrit la méthode de
faisceaux réalisée. La résolution du problème quadratique est détaillée,
dans le cas d'un problème non contraint et dans le cas d'un problème avec
contraintes de bornes. Le traitement de contraintes convexes et
d'objectifs désagrégés dans le programme quadratique sont évoqués. Les
études numériques réalisées ont permis de mettre en évidence un choix de
paramètres robuste et de préciser la validité de deux critères d'arrêt.
La troisième partie concerne un problème de dimensionnement de réseau de
télécommunications. L'objectif est de minimiser des coûts d'investissements
sur plusieurs années successives. Le réseau obtenu à chaque période
successive doit permettre de faire transiter toutes les demandes de trafic.
Différentes approches pour le choix des investissements ont été comparées
sur des réseaux de dix à quinze villes. On part d'une modélisation par
Programmation Linéaire en Nombres Entiers et on propose plusieurs
techniques de décomposition,
dont une relaxation lagrangienne. Une approche par réseau cible a permis
d'obtenir des solutions réalisables en un temps raisonnable.