MAMANE SOULEYE Ibrahim

毕业博士
科研组 : DECISION
离开日期 : 2007-12-20
https://lip6.fr/Ibrahim.Mamane-Souleye

责任导师 : 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.

答辩 : 2007-12-19

评委会 :

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)

离开日期 : 2007-12-20

2007 刊物

Mentions légales
网站导航