Dans ce livre, on s'int resse au probl me du plus court chemin entre deux sommets donn s dans des graphes orient s pouvant comporter des circuits absorbants. On commence par tudier des formulations de ce probl me en programmation lin aire variables enti res et mixtes. Une des formulations, dite "compacte," a le 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. On montre la difficult potentielle li e au probl me de s paration de ces in galit s. En revanche, combin es des techniques de lifting, ces in galit s valides seront exploitables. 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 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.