Problème de flux à coût minimum - Minimum-cost flow problem

Le problème de flux à coût minimum ( MCFP ) est un problème d' optimisation et de décision visant à trouver le moyen le moins cher possible d'envoyer une certaine quantité de flux à travers un réseau de flux . Une application typique de ce problème consiste à trouver le meilleur itinéraire de livraison d'une usine à un entrepôt où le réseau routier a une certaine capacité et des coûts associés. Le problème de flux à coût minimum est l'un des plus fondamentaux parmi tous les problèmes de flux et de circulation car la plupart des autres problèmes de ce type peuvent être considérés comme un problème de flux à coût minimum et aussi qu'il peut être résolu efficacement en utilisant l' algorithme du simplexe du réseau .

Définition

Un réseau de flux est un graphe orienté avec un sommet source et un sommet puits , où chaque arête a une capacité , un flux et un coût , la plupart des algorithmes de flux à coût minimum prenant en charge les arêtes à coûts négatifs. Le coût d'envoi de ce flux le long d'une arête est de . Le problème nécessite qu'une quantité de flux soit envoyée de la source au puits . ${\style d'affichage G=(V,E)}$${\displaystyle s\in V}$${\displaystyle t\in V}$${\style d'affichage (u,v)\dans E}$${\style d'affichage c(u,v)>0}$${\style d'affichage f(u,v)\geq 0}$${\style d'affichage a(u,v)}$${\style d'affichage (u,v)}$${\style d'affichage f(u,v)\cdot a(u,v)}$${\style d'affichage d}$${\style d'affichage s}$${\style d'affichage t}$

La définition du problème est de minimiser le coût total de l'écoulement sur toutes les arêtes :

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$

avec les contraintes

Contraintes de capacité :	${\style d'affichage \,f(u,v)\leq c(u,v)}$
Symétrie asymétrique :	${\style d'affichage \,f(u,v)=-f(v,u)}$
Conservation du débit :	${\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{ pour tout }}u\neq s,t}$
Débit requis :	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ et }}\sum _{w\in V}f(w,t)=d}$

Relation avec d'autres problèmes

Une variante de ce problème consiste à trouver un débit qui est maximal, mais qui a le coût le plus bas parmi les solutions de débit maximal. Cela pourrait être appelé un problème de flux maximum à coût minimum et est utile pour trouver des correspondances maximum à coût minimum .

Avec certaines solutions, il est plutôt simple de trouver le débit maximal à coût minimum. Sinon, on peut trouver le débit maximum en effectuant une recherche binaire sur . ${\style d'affichage d}$

Un problème connexe est le problème de circulation à coût minimum , qui peut être utilisé pour résoudre le flux à coût minimum. Ceci est réalisé en définissant la limite inférieure sur toutes les arêtes à zéro, puis en créant une arête supplémentaire du puits à la source , avec une capacité et une limite inférieure , forçant le flux total de à à être également . ${\style d'affichage t}$${\style d'affichage s}$${\style d'affichage c(t,s)=d}$${\style d'affichage l(t,s)=d}$${\style d'affichage s}$${\style d'affichage t}$${\style d'affichage d}$

Les problèmes suivants sont des cas particuliers du problème de flux de coût minimum (nous fournissons à tour de rôle de brefs croquis de chaque réduction applicable) :

• Problème de chemin le plus court (source unique). Exiger qu'une solution réalisable au problème de flux de coût minimum envoie une unité de flux d'une source désignée à un puits désigné . Donnez à tous les bords une capacité infinie.${\style d'affichage s}$${\style d'affichage t}$
• Problème de débit maximum . Supposons que tous les nœuds aient une demande nulle et que le coût associé à la traversée de n'importe quel bord soit nul. Maintenant, introduisez une nouvelle arête du puits actuel vers la source actuelle . Précisez que le coût unitaire de l'envoi de flux à travers la périphérie est égal à , et autorisez une capacité infinie. (Cette réduction est également mentionnée dans Problème de circulation ).${\style d'affichage (t,s)}$${\style d'affichage t}$${\style d'affichage s}$${\style d'affichage (t,s)}$${\style d'affichage -1}$${\style d'affichage (t,s)}$
• Problème d'affectation . Supposons que chaque ensemble de partitions dans la bipartition a des sommets et notez la bipartition par . Donnez chaque offre et donnez chaque demande . Chaque bord doit avoir une capacité unitaire.${\style d'affichage n}$${\style d'affichage (X,Y)}$${\style d'affichage x\dans X}$${\style d'affichage 1/n}$${\displaystyle y\in Y}$${\style d'affichage 1/n}$

Solutions

Le problème de flux de coût minimum peut être résolu par programmation linéaire , car nous optimisons une fonction linéaire et toutes les contraintes sont linéaires.

En dehors de cela, de nombreux algorithmes combinatoires existent, pour une étude complète, voir . Certains d'entre eux sont des généralisations d' algorithmes de débit maximum , d'autres utilisent des approches totalement différentes.

Algorithmes fondamentaux bien connus (ils ont de nombreuses variantes) :

• Annulation de cycle : une méthode primale générale.
• Annulation de coupe : une méthode double générale.
• Annulation du cycle moyen minimum : un algorithme simple fortement polynomial .
• Chemin le plus court successif et mise à l'échelle de la capacité : méthodes duales, qui peuvent être considérées comme la généralisation de l' algorithme de Ford-Fulkerson .
• Mise à l'échelle des coûts : une approche primale-duale, qui peut être considérée comme la généralisation de l' algorithme push-relabel .
• Algorithme de simplex de réseau : une version spécialisée de la méthode de simplex de programmation linéaire .
• Algorithme déséquilibré par DR Fulkerson

Application

Correspondance bipartite de poids minimum

Réduction de l'appariement bipartite du poids minimum au problème de flux maximum de coût minimum

Étant donné un graphe bipartite G = ( A ∪ B , E ) , le but est de trouver la correspondance de cardinalité maximale dans G qui a un coût minimal. Soit w : E → R une fonction de poids sur les arêtes de E . Le poids minimum de problème correspondant bipartite ou problème d'affectation est de trouver une correspondance parfaite M ⊆ E dont le poids total est réduit au minimum. L'idée est de réduire ce problème à un problème de flux de réseau.

Soit G ' = ( V' = A ∪ B , E ' = E ) . Attribuez la capacité de toutes les arêtes de E′ à 1. Ajoutez un sommet source s et connectez-le à tous les sommets de A′ et ajoutez un sommet puits t et connectez tous les sommets à l'intérieur du groupe B′ à ce sommet. La capacité de toutes les nouvelles arêtes est de 1 et leur coût est de 0. Il est prouvé qu'il y a un appariement bipartite parfait de poids minimum dans G si et seulement s'il y a un flux de coût minimum dans G′ .

Voir également

• CITRON (bibliothèque C++)
• Kit de programmation linéaire GNU

Les références

1. ^ Ravindra K. Ahuja ; Thomas L. Magnanti & James B. Orlin (1993). Flux de réseau : théorie, algorithmes et applications . Prentice-Hall, Inc. ISBN 978-0-13-617549-0.
2. ^ Morton Klein (1967). « Une méthode primaire pour des flux de coûts minimaux avec des applications aux problèmes d'affectation et de transport ». Sciences de gestion . 14 (3) : 205-220. CiteSeerX  10.1.1.228.7696 . doi : 10.1287/mnsc.14.3.105 .
3. ^ Refael Hassin (1983). « Le problème de flux de coût minimum : Une approche unificatrice des algorithmes existants et un nouvel algorithme de recherche arborescente ». Programmation mathématique . 25 : 228-239. doi : 10.1007/bf02591772 .
4. ^ Thomas R. Ervolina et S. Thomas McCormick (1993). "Deux algorithmes d'annulation de coupure fortement polynomiaux pour un flux de réseau à coût minimum" . Mathématiques discrètes appliquées . 4 : 133-165. doi : 10.1016/0166-218x(93)90025-j .
5. ^ Andrew V. Goldberg et Robert E. Tarjan (1989). "Trouver des circulations à coût minimum en annulant les cycles négatifs". Journal de l'ACM . 36 (4) : 873-886. doi : 10.1145/76359.76368 .
6. ^ Jack Edmonds et Richard M. Karp (1972). « Améliorations théoriques de l'efficacité algorithmique pour les problèmes de flux de réseau ». Journal de l'ACM . 19 (2) : 248-264. doi : 10.1145/321694.321699 .
7. ^ Andrew V. Goldberg et Robert E. Tarjan (1990). « Trouver des circulations à coût minimum par approximations successives ». Math. Oper. Rés . 15 (3) : 430-466. doi : 10.1287/moor.15.3.430 .
8. ^ James B. Orlin (1997). « Un algorithme simplex de réseau primal à temps polynomial pour des flux de coûts minimaux ». Programmation mathématique . 78 (2) : 109-129. doi : 10.1007/bf02614365 . hdl : 1721.1/2584 .

Liens externes

• Bibliothèque LEMON C++ avec plusieurs algorithmes de circulation à débit maximum et à coût minimum
• La bibliothèque de projet MCFClass C++ avec des algorithmes de flux de coût minimum et de chemin le plus court