Le Probl me Du Plus Court Chemin Avec Des Longueurs N gatives : Formulations et inégalités valides

Dans ce livre, on s'intresse au problme du plus court chemin entre deux sommets donns dans des graphes orients pouvant comporter des circuits absorbants. On commence par tudier des formulations de ce problme en programmation linaire variables entires et mixtes. Une des formulations, dite "compacte", a le double avantage de ncessiter un nombre polynomial de contraintes et de constituer, comme le montrent nos exprimentations, une relaxation plus forte en moyenne. Dans le but de rsoudre le problme efficacement, on tudie ensuite la possibilit de gnrer des ingalits valides. On montre la difficult potentielle lie au problme de sparation de ces ingalits. En revanche, combines des techniques de lifting, ces ingalits valides seront exploitables. Nos exprimentations effectues sur une srie de graphes de tailles allant jusqu' 200 sommets montrent en particulier que le renforcement itratif par les ingalits liftes permet d'obtenir la solution optimale entire en moins de dix itrations pour plus de 50% des exemples considrs. Mots cls : Programmation linaire, Graphe, Plus court chemin, Ingalits valides, Sparation, Lifting.