16 127 528 książek w 175 językach
Jednak się nie przyda? Nic nie szkodzi! U nas możesz zwrócić towar do 30 dni
Bon prezentowy to zawsze dobry pomysł. Obdarowany może za bon prezentowy wybrać cokolwiek z naszej oferty.
30 dni na zwrot towaru
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.