Le Problème Du Plus Court Chemin Avec Des Longueurs Négatives » książka
Le Problème Du Plus Court Chemin Avec Des Longueurs Négatives
ISBN-13: 9783841749123 / Francuski / Miękka / 2018 / 144 str.
Dans ce livre, on s'intA(c)resse au problA]me du plus court chemin entre deux sommets donnA(c)s dans des graphes orientA(c)s pouvant comporter des circuits absorbants. On commence par A(c)tudier des formulations de ce problA]me en programmation linA(c)aire A variables entiA]res et mixtes. Une des formulations, dite compacte, a le double avantage de nA(c)cessiter un nombre polynomial de contraintes et de constituer, comme le montrent nos expA(c)rimentations, une relaxation plus forte en moyenne. Dans le but de rA(c)soudre le problA]me efficacement, on A(c)tudie ensuite la possibilitA(c) de gA(c)nA(c)rer des inA(c)galitA(c)s valides. On montre la difficultA(c) potentielle liA(c)e au problA]me de sA(c)paration de ces inA(c)galitA(c)s. En revanche, combinA(c)es A des techniques de lifting, ces inA(c)galitA(c)s valides seront exploitables. Nos expA(c)rimentations effectuA(c)es sur une sA(c)rie de graphes de tailles allant jusqu'A 200 sommets montrent en particulier que le renforcement itA(c)ratif par les inA(c)galitA(c)s liftA(c)es permet d'obtenir la solution optimale entiA]re en moins de dix itA(c)rations pour plus de 50% des exemples considA(c)rA(c)s. Mots clA(c)s: Programmation linA(c)aire, Graphe, Plus court chemin, InA(c)galitA(c)s valides, SA(c)paration, Lifting.
Dans ce livre, on sinté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 dobtenir 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.
Czytaj nas na:
KrainaKsiazek.PL - Księgarnia Internetowa
