Le Probleme Du Plus Court Chemin Avec Des Longueurs Negatives

Dans ce livre, on s'interesse au probleme du plus court chemin entre deux sommets donnes dans des graphes orientes pouvant comporter des circuits absorbants. On commence par etudier des formulations de ce probleme en programmation lineaire a variables entieres et mixtes. Une des formulations, dite compacte, a le double avantage de necessiter un nombre polynomial de contraintes et de constituer, comme le montrent nos experimentations, une relaxation plus forte en moyenne. Dans le but de resoudre le probleme efficacement, on etudie ensuite la possibilite de generer des inegalites valides. On montre la difficulte potentielle liee au probleme de separation de ces inegalites. En revanche, combinees a des techniques de lifting, ces inegalites valides seront exploitables. Nos experimentations effectuees sur une serie de graphes de tailles allant jusqu'a 200 sommets montrent en particulier que le renforcement iteratif par les inegalites liftees permet d'obtenir la solution optimale entiere en moins de dix iterations pour plus de 50% des exemples consideres. Mots cles: Programmation lineaire, Graphe, Plus court chemin, Inegalites valides, Separation, Lifting.