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

Membres du jury :

Ridha Ali Mahjoub : professeur (Paris IX) [rapporteur]
Leslie Trotter : Professeur (Cornell university, NY) [rapporteur]
Patrice Perny: professeur (UPMC - LIP6)
Viet Hung Nguyen: maître de conférence (UPMC-LIP6)
Michel Minoux: professeur (UPMC - LIP6)

Publications 2007

• 2007
  • I. Mamane Souleye : “Étude de formulations et inégalités valides pour le problème du plus court chemin dans les graphes avec des circuits absorbants”, soutenance de thèse, soutenance 19/12/2007, direction de recherche Minoux, Michel (2007)