Problem des minimalen Kostenflusses

Das Problem des minimalen Kostenflusses ( MCFP ) ist ein Optimierungs- und Entscheidungsproblem , das den kostengünstigsten Weg zum Transport einer bestimmten Warenmenge durch ein Flussnetzwerk sucht. Eine typische Anwendung ist die Suche nach der optimalen Lieferroute von einer Fabrik zu einem Lager, wobei das Straßennetz über eine bestimmte Kapazität und damit verbundene Kosten verfügt. Das Problem des minimalen Kostenflusses zählt zu den grundlegendsten aller Fluss- und Zirkulationsprobleme, da sich die meisten anderen Probleme dieser Art als solches formulieren und effizient mit dem Netzwerk-Simplex-Algorithmus lösen lassen .

Ein Flussnetzwerk ist ein gerichteter Graph mit einem Quellknoten und einem Zielknoten , wobei jede Kante eine Kapazität , einen Fluss und Kosten besitzt . Die meisten Algorithmen zur Berechnung minimaler Flusskosten unterstützen Kanten mit negativen Kosten. Die Kosten für das Senden dieses Flusses entlang einer Kante betragen . Das Problem erfordert, dass eine bestimmte Flussmenge von der Quelle zur Zieladresse gesendet wird . ${\displaystyle G=(V,E)}$${\displaystyle s\in V}$${\displaystyle t\in V}$${\displaystyle (u,v)\in E}$${\displaystyle c(u,v)>0}$${\displaystyle f(u,v)}$${\displaystyle a(u,v)}$${\displaystyle (u,v)}$${\displaystyle f(u,v)\cdot a(u,v)}$${\displaystyle d}$${\displaystyle s}$${\displaystyle t}$

Die Problemdefinition besteht darin, die Gesamtkosten des Flusses über alle Kanten zu minimieren:

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

unter den Einschränkungen

Kapazitätsbeschränkungen :	${\displaystyle \,f(u,v)\leq c(u,v)}$
Schiefe Symmetrie :	${\displaystyle \,f(u,v)=-f(v,u)}$
Durchflusserhaltung :	${\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{ für alle }}u\neq s,t}$
Erforderlicher Ablauf :	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ und }}\sum _{w\in V}f(w,t)=d}$

Eine Variante dieses Problems besteht darin, einen maximalen Fluss zu finden, der unter den Lösungen mit maximalem Fluss die geringsten Kosten aufweist. Dies könnte man als Problem des minimalen Kosten-Maximalflusses bezeichnen und es ist nützlich, um minimale Kosten-Maximal- Matchings zu finden .

Bei manchen Lösungen lässt sich der minimale Kosten-Maximalfluss direkt ermitteln. Andernfalls kann man den maximalen Fluss durch eine binäre Suche finden . ${\displaystyle d}$

Ein verwandtes Problem ist das Zirkulationsproblem mit minimalen Kosten , das zur Lösung von Flussproblemen mit minimalen Kosten verwendet werden kann. Dieses Problem kennt keine Quelle und Senke; stattdessen existieren Kosten sowie untere und obere Schranken für jede Kante. Gesucht werden Flussmengen innerhalb dieser Grenzen, die den Fluss an jedem Knoten ausgleichen und die Summe der Kosten mal Fluss über alle Kanten minimieren. Jede Flussproblematik mit minimalen Kosten lässt sich in eine Zirkulationsproblematik mit minimalen Kosten umwandeln, indem die untere Schranke aller Kanten auf null gesetzt und anschließend eine zusätzliche Kante von der Senke zur Quelle mit der Kapazität und der unteren Schranke erstellt wird . Dadurch wird der Gesamtfluss von der Senke zur Quelle auf den Wert gesetzt . ${\displaystyle t}$${\displaystyle s}$${\displaystyle c(t,s)=d}$${\displaystyle l(t,s)=d}$${\displaystyle s}$${\displaystyle t}$${\displaystyle d}$

Die folgenden Probleme sind Spezialfälle des Problems des minimalen Kostenflusses (wir geben nacheinander kurze Skizzen der jeweils anwendbaren Reduktionen an): ^{[ 1 ]}

• Kürzeste-Wege-Problem (von einer Quelle aus). Die zulässige Lösung des Kostenflussproblems soll eine Flusseinheit von einer vorgegebenen Quelle zu einer vorgegebenen Senke transportieren . Alle Kanten sollen unbegrenzte Kapazität haben.${\displaystyle s}$${\displaystyle t}$
• Maximales Flussproblem . Wähle eine große Nachfrage (groß genug, um den maximalen Fluss zu überschreiten; zum Beispiel die Summe der Kapazitäten vom Quellknoten aus). Setze die Kosten aller Kanten in der maximalen Flussinstanz auf Null und füge eine neue Kante von der Quelle zur Senke mit Einheitskosten und Kapazität hinzu .${\displaystyle d}$${\displaystyle d}$
• Zuordnungsproblem . Angenommen, jede Partition in der Bipartition hat Knoten, und die Bipartition wird mit bezeichnet . Jeder Angebotsmenge werden und jeder Nachfragemenge zugeordnet . Jede Kante soll eine Kapazität von 1 haben.${\displaystyle n}$${\displaystyle (X,Y)}$${\displaystyle x\in X}$${\displaystyle 1/n}$${\displaystyle y\in Y}$${\displaystyle 1/n}$

Das Problem des minimalen Kostenflusses kann durch lineare Programmierung gelöst werden , da wir eine lineare Funktion optimieren und alle Nebenbedingungen linear sind.

Abgesehen davon existieren viele kombinatorische Algorithmen. ^{[ 1 ]} Einige von ihnen sind Verallgemeinerungen von Algorithmen zur Berechnung des maximalen Flusses , andere verwenden völlig unterschiedliche Ansätze.

Bekannte fundamentale Algorithmen (es gibt viele Varianten):

• Zyklusunterdrückung : eine allgemeine primale Methode. ^{[ 2 ]}
• Schnittkürzung : eine allgemeine duale Methode. ^{[ 3 ] [ 4 ]}
• Minimale mittlere Zykluskompensation : ein einfacher, stark polynomieller Algorithmus. ^{[ 5 ]}
• Sukzessive kürzeste Wege und Kapazitätsskalierung : duale Methoden, die als Verallgemeinerung des Ford-Fulkerson-Algorithmus betrachtet werden können . ^{[ 6 ]}
• Kostenskalierung : ein primal-dualer Ansatz, der als Verallgemeinerung des Push-Relabel-Algorithmus betrachtet werden kann . ^{[ 7 ]}
• Netzwerk-Simplex-Algorithmus : eine spezialisierte Version der linearen Programmierungs- Simplex-Methode . ^{[ 8 ]}
• Aus dem Gleichgewicht geratener Algorithmus von DR Fulkerson

Diese Algorithmen sind iterativ und definieren, ähnlich dem Ford-Fulkerson-Algorithmus, einen Restgraphen. Existiert ein Fluss auf einem Bogen , so ist seine Restkapazität definiert als und seine Restkosten als . Der umgekehrte Bogen (mit negativem Flusswert) hat negative Kosten . Die Algorithmen beginnen mit einem beliebigen zulässigen Fluss und verbessern iterativ die Kosten der Lösung, indem sie den Fluss um Zyklen mit negativen Kosten herumleiten. Beim Algorithmus zur Minimierung der mittleren Zykluskosten wählt der Algorithmus einen Zyklus mit minimalen mittleren Kosten (dem Verhältnis der gesamten Zykluskosten zur Anzahl der Bögen). Ein solcher Zyklus kann in Polynomialzeit gefunden werden (mittels binärer Suche mit dem Bellman-Ford-Algorithmus ), und die Gesamtzahl der Iterationen ist nachweislich polynomiell ^{[ 5 ]} . ${\displaystyle f(u,v)}$${\displaystyle e=(u,v)}$${\displaystyle c(e)-f(e)}$${\displaystyle a(e)}$${\displaystyle -a(e)}$

Gegeben sei ein bipartiter Graph G = ( A ∪ B , E ) . Ziel ist es, das Matching mit maximaler Kardinalität in G zu finden , das minimale Kosten aufweist. Sei w : E → R eine Gewichtsfunktion auf den Kanten von E. Das Problem des minimalen Gewichts bipartiter Matchings bzw. Zuordnungsproblems besteht darin, ein perfektes Matching M ⊆ E zu finden , dessen Gesamtgewicht minimiert wird. Die Idee ist, dieses Problem auf ein Netzwerkflussproblem zu reduzieren.

Sei G′ = ( V′ = A ∪ B , E′ = E ) . Weise allen Kanten in E′ die Kapazität 1 zu. Füge einen Quellknoten s hinzu und verbinde ihn mit allen Knoten in A′. Füge außerdem einen Senkenknoten t hinzu und verbinde alle Knoten innerhalb der Gruppe B′ mit diesem Knoten. Die Kapazität aller neuen Kanten ist 1 und ihre Kosten sind 0. Es ist bewiesen, dass es genau dann ein perfektes bipartites Matching minimalen Gewichts in G gibt , wenn es einen Fluss minimaler Kosten in G′ gibt . ^{[ 1 ]}

• LEMON (C++-Bibliothek)
• GNU Linear Programming Kit
• Netzwerkflussproblem

• LEMON C++-Bibliothek mit mehreren Algorithmen zur Maximierung des Durchflusses und zur Minimierung der Kosten
• Die MCFClass C++-Projektbibliothek mit einigen Algorithmen für minimalen Kostenfluss und kürzesten Pfad.