Algorithme de flot maximal à coût minimal

Bonjour,
Pour un projet, je dois implémenter ce type d'algorithme. Seulement je trouve la littérature tres limitée sur ce sujet.
Pour l'instant, j'ai implémenté Dijskra, Bellman-Kalaba et Ford Fulkerson (la version pour les couts minimaux).
Je me demande si vous pourriez m'indiquer d'autres algorithmes de flot max à cout min et meme d'autres algorithmes de plus court chemin pour donner plus de choix à l'utilisateur.
Pour le plus court chemin, j'ai pensé à A(*), pour lequel on peut trouver facilement le fonctionnement. Par contre l' algorithme de Busacker-Gowen ou celui de Klein par exemple dont on retrouve le nom parfois, impossible de mettre la main sur son fonctionnement.

Merci d'avance.

Le livre référence à ce sujet est network flows de Ahuja, Magnanti et Orlin

Un lien intéressant à ce sujet sont les transparents de cours très bien faits de Jim Orlin:
http://web.mit.edu/jorlin/www/15.082...abus_2003.html

Tu pourrais t'intéresser aux algorithmes de préflots qui donnent une autre approche. Le chapitre 8 de ce livre en ligne devrait ainsi t'intéresser
http://www-igm.univ-mlv.fr/%7Eberste.../Elements.html

A titre de curiosité, tu pourras aussi être intéressé par une librairie existante qui implémente un grand nombre d'algo de graphes. Il s'agit de Goblin

http://www.math.uni-augsburg.de/~fremuth/goblin.html

Bonjour,

Pour poser une question en rapport avec ce topic,

Qq'un a-t-il déjà testé les performances d'un algorithme de flot max de coût min contre un solveur MIP ?

J'ai codé, pour un problème de flot max à coût min, l'algorithme de Busacker et Gowen, et l'algorithme primal-dual. Leurs résultats sont assez mauvais en comparaison d'un solveur commercial (Ilog Cplex 9.1). Pour mon cas, Cplex résout une instance en 80 ms et l'algo de flot primal-dual en 1488ms, avec un graphe de 1202 sommets et 2695 arcs.

Je dois tout de même ajouter que mon graphe a une structure spécifique : il est décomposable en 5 niveaux, et seuls les arcs allant du niveau 3 vers le niveau 4 ont des valuations différentes de 0.

Bref, que pensez-vous de mon constat ?
- Le solveur est meilleur sur les pbs de flot max de coût min en général ?
- Le solveur est meilleur sur les pbs de flot max de coût min sur mon cas particulier ?
- Mes résultats numériques pour les algos paraissent trop élevés, mon code n'est pas optimisé, 1488 ms pour un graphe de 1202 sommets et 2695 arcs est trop élevé ? [remarque : mon code ne tient pas compte des spécificités du graphe]

Vos remarques et conseils seront les bienvenus :-)
Merci !

Le truc avec les problèmes de flots c'est que leur matrice de contraintes est totalement unimodulaire, ça implique que la relaxation linéaire du MIP est optimale (les solutions du polytope sont à coordonnées entières). Il faut donc déjà que ton implémentation du Busacker et Gowen "batte" la résolution d'un PL par Cplex (déjà, c'est pas gagné...).

Faudrait voir mais je pense en plus que Cplex doit être capable de détecter la structure de flot du PL (de là à dire qu'ils ont implémenté des algos dédiés...)

Sinon pour l'algo du flot max à coût min, as-tu implémenté celui de Goldberg et Tarjan (1989) celui où l'on recherche un circuit de longueur moyen minimum sur le graphe d'écart? Il me semble que c'est celui avec la meilleur complexité.

J'avais fait les même comparaisons que toi et après une intense phase d'optimisation de mon code, je n'avais toujours pas réussi à battre Cplex...

Moralité... : sauf cas particulier, je te conseillerai d'utiliser un solveur, c'est plus rapide à développer et t'es sûr en plus que c'est pas buggé le tout avec des performances (quasi) optimales (tu devrais aussi faire le test comparatif avec un solveur gratuit genre glpk ou lpsolve...)

Merci pour ta réponse CedricMocquillon :-)

Je n'ai pas codé l'algorithme de Goldberg et Tarjan (1989) parce que, et bien, je ne le connaissais pas :-) J'avais cru entendre que l'algo de flot primal-dual était celui de meilleure complexité en moyenne, mais bon, j'ai peut être mal entendu ?

Enfin bref, peu importe, je crois aussi que Cplex a mis en place des outils pour vérifier la structure de flot. Donc, je pense que ça va être dur de le battre. Tu me confortes d'autant plus dans cette idée que tu as déjà essayé.

C'est vrai aussi que la totale unimodularité est plus propice au solveur mais bon, j'avais tout de même un peu espoir, si on regarde le pb de flot max par exemple, on arrive encore à battre les solveurs.

Merci en tout cas pour tes remarques, je vais t'écouter et ne pas galérer à optimiser mon code pour pas grand chose, à moins que qq'un ne me convainque du contraire :-)