MAMANE SOULEYE Ibrahim

Docteur
Équipe : DECISION
Date de départ : 20/12/2007
Direction de recherche : Michel MINOUX

Étude de formulations et inégalités valides pour le problème du plus court chemin dans les graphes avec des circuits absorbants

Dans ce travail, on s'intéresse au problème du plus court chemin entre deux sommets donnés dans les graphes orientés pouvant comporter des circuits négatifs. On commence par étudier des formulations de ce problème en programmation linéaire à variables entières et mixtes. Une première formulation, inspirée de celle classique du problème du voyageur de commerce, fait intervenir un nombre exponentiel de contraintes. Nous étudions une seconde formulation dite "compacte" ayant un double avantage de nécessiter un nombre polynomial de contraintes et de constituer, comme le montrent nos expérimentations, une relaxation plus forte en moyenne. Dans le but de résoudre le problème efficacement, on étudie ensuite la possibilité de générer des inégalités valides. Nous proposons plusieurs classes de telles inégalités susceptibles de renforcer la relaxation linéaire. On montre l'aspect NP-difficile du problème de séparation de ces inégalités. En revanche, combinées à des techniques de lifting, ces inégalités seront exploitables. Nous proposons ainsi une technique de lifting de ces inégalités valides générées sur des sous graphes. En fonction du sous graphe considéré, on met en oeuvre deux types d'inégalités valides liftées, à savoir celles qui sont dites "liftées simples" et les "liftées de cocycle". Nos expérimentations effectuées sur une série de graphes de tailles allant jusqu'à 200 sommets montrent en particulier que le renforcement itératif par les inégalités liftées simples permet d'obtenir la solution optimale entière en moins de dix itérations pour plus de 50% des exemples considérés. Mots clés: Programmation linéaire, Graphe, Plus court chemin, Inégalités valides, Séparation, Lifting.
Soutenance : 19/12/2007 - 14h30 - Site Passy-Kennedy - salle 549
Membres du jury :
- Patrice Perny: professeur (UPMC - LIP6) : examinateur
- Ridha Ali Mahjoub : professeur (Paris IX) : rapporteur
- Leslie Trotter : Professeur (Cornell university, NY) : rapporteur
- Viet Hung Nguyen: maître de conférence (UPMC-LIP6) : examinateur
- Michel Minoux: professeur (UPMC - LIP 6) : directeur de thèse

Publications 2007

 Mentions légales
Carte du site |