IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme de flot maximal à coût minimal


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Inscrit en
    Mai 2006
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 15
    Points : 7
    Points
    7
    Par défaut 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.

  2. #2
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554
    Par défaut
    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

  3. #3
    Membre du Club
    Inscrit en
    Mai 2004
    Messages
    59
    Détails du profil
    Informations forums :
    Inscription : Mai 2004
    Messages : 59
    Points : 50
    Points
    50
    Par défaut
    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 !

  4. #4
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 301
    Points : 345
    Points
    345
    Par défaut
    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...)

  5. #5
    Membre du Club
    Inscrit en
    Mai 2004
    Messages
    59
    Détails du profil
    Informations forums :
    Inscription : Mai 2004
    Messages : 59
    Points : 50
    Points
    50
    Par défaut
    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 :-)

Discussions similaires

  1. Problème de flot à coût minimal à l'aide d'un réseau
    Par jojoo08 dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 06/04/2013, 22h42
  2. Algorithme sur le flot maximal de Ford Fulkerson
    Par witch dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 13/05/2011, 16h57
  3. Réponses: 2
    Dernier message: 05/02/2007, 20h37
  4. Logiciel pour calculer le flot maximal
    Par Yakurena dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 05/03/2006, 13h47
  5. Maximize et Minimize perso...
    Par Antomax dans le forum API, COM et SDKs
    Réponses: 5
    Dernier message: 16/06/2004, 17h40

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo