Tous nos rayons

Déjà client ? Identifiez-vous

Mot de passe oublié ?

Nouveau client ?

CRÉER VOTRE COMPTE
Le problème du plus court chemin avec des longueurs négatives
Ajouter à une liste

Librairie Eyrolles - Paris 5e
Indisponible

Le problème du plus court chemin avec des longueurs négatives

Le problème du plus court chemin avec des longueurs négatives

Collectif - Collection Omn.univ.europ.

144 pages, parution le 19/05/2015

Résumé

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.

Caractéristiques techniques

  PAPIER
Éditeur(s) Editions universitaires européennes
Auteur(s) Collectif
Collection Omn.univ.europ.
Parution 19/05/2015
Nb. de pages 144
Format 15.2 x 22.9
Couverture Broché
Poids 222g
EAN13 9783841749123

Avantages Eyrolles.com

Livraison à partir de 0,01 en France métropolitaine
Paiement en ligne SÉCURISÉ
Livraison dans le monde
Retour sous 15 jours
+ d'un million et demi de livres disponibles
satisfait ou remboursé
Satisfait ou remboursé
Paiement sécurisé
modes de paiement
Paiement à l'expédition
partout dans le monde
Livraison partout dans le monde
Service clients sav@commande.eyrolles.com
librairie française
Librairie française depuis 1925
Recevez nos newsletters
Vous serez régulièrement informé(e) de toutes nos actualités.
Inscription