Minimum-Cost Flow Problem

Das Minimum-Cost Flow Problem oder Min-Cost-Flow-Problem ist ein Optimierungs- und Entscheidungsproblem aus der Klasse der Netzwerkflussprobleme und ist eine allgemeine Methode für die Modellierung und Lösung des Umlade- bzw. des Transportproblems.^[1] Probleme dieser Art wurden bereits 1781 von dem französischen Mathematiker Gaspard Monge formuliert^[2] und erhielten während der Aufrüstung im Kalten Krieg auf Grund der militärischen Relevanz der Transportlogistik des Nachschubs eine verstärkte Aufmerksamkeit.^[3] Das Ziel ist es, gegeben eine Kostenfunktion für den Transport von Gütern, die günstigste Möglichkeit für den Transport von einem oder mehreren Startpunkten (Quellen) durch ein Netzwerk zu einem oder mehreren Zielpunkten (Senken) zu bestimmen. Je nach Struktur der Kostenfunktion ist das Problem NP-schwer oder es existieren polynomiell exakte Algorithmen. Im Allgemeinen ist die Lösung von Min-Cost-Flow Problemen nicht eindeutig.

Problem Formulierung

Ein Fluss Netzwerk ist ein gerichteter Graph $G=(V,E)$ zusammen mit einem Startknoten $s\in V$ mit dem Angebot $a\in \mathbb {R} ^{+}$ und einen Zielknoten $t\in V$ mit einer, dem Angebot entsprechenden Nachfrage $-a$ , sowie 2 Funktionen, die auf der Kantenmenge definiert sind:

Die Kapazitätsfunktion $\kappa :E\rightarrow \mathbb {R} ^{+}$ weist jeder Kante zu, wie viel Güter maximal entlang der Kante transportiert werden können.
Die Flussfunktion $f:E\rightarrow \mathbb {R} _{0}^{+}$ weist jeder Kante zu wieviel Güter tatsächlich für den Transport allokiert werden. Daher gilt auch die Kapazitätsbeschränkung $f(u,v)\leq \kappa (u,v)$ für alle $v,u\in V$ .

Darüber hinaus müssen für die Flussfunktion die folgenden 2 Eigenschaften gelten:

Die Flusserhaltung, welche sich für alle $u\neq s,t$ durch $\,\sum _{w\in V}f(u,w)=0$ ausdrücken lässt.
Die Flusserfüllung von Angebot und Nachfrage, die sich für den Startknoten durch $\,\sum _{w\in V}f(s,w)=d$ und den Zielknoten durch $\,\sum _{w\in V}f(w,t)=d$ ausdrücken lässt.

Führt man zusätzlich eine (trennbare) Kostenfunktion $c:E\times \mathbb {R} \rightarrow \mathbb {R} _{0}^{+}$ ein, die jeder Kante in Abhängigkeit des allokierten Flusswertes einen Wert für die Transportkosten zuweist berechnet man die Gesamtkosten des Flusses $f$ mit Hilfe der Kostenformel $\,C(f)=\sum _{(u,v)\in E}c(u,v,f(u,v))$ .

Bei einem Min-Cost Flow Problem sucht man eine Flussfunktion, welche die Kostenformel minimiert.

Komplexität und Struktur der Kostenfunktion

Die Kapazitätsbeschränkung, Flusserhaltung und Flusserfüllung machen das Auffinden einer Flussfunktion, die die Kostenformel minimiert zu einem Optimierungsproblem mit Zwangsbedingungen. Daher könnte man das Problem zumindest in der Theorie numerisch mit der Mode der Lagrange-Multiplikatoren lösen. In der Praxis entstehen dabei jedoch in der Regel Funktionen, die so stark nicht linear sind, dass das Finden einer Lösung mit numerischen Methoden oft impraktikabel wird. Im Bereich der Informatik und des Operation Research wurden seit den späten 1960er Jahren Algorithmen und Verfahren für die exakte Lösung dieser Problemklasse entwickelt.^[4] Diese Lösungen existieren häufig in dem weitere Annahmen an das Problem gestellt werden. So wird das Problem im diskreten Fall, bei dem die Kapazitäts- und Fluss Funktion nur natürliche Zahlen oder den Wert 0 annimmt deutlich leichter zu berechnen.

Lineare Kostenfunktion

Im Fall einer linearen Kostenfunktion lässt sich das Problem durch Techniken der Linearen Programmierung und mit Hilfe des Simplex-Verfahrens lösen.

Konvexe Kostenfunktion

1986 zeigte Minoux, dass für den diskreten Fall polynomiell exakte Lösungen für das Problem im Falle einer konvexen Kostenfunktion existieren.^[5] Diese können zum Beispiel gefunden werden, indem die Kostenfunktion in den einzelnen Delta-Phasen des Capacity-Scaling Algorithmus stückweise linearisiert wird.^[3]

Allgemeine nichtlineare Kostenfunktion

Für allgemeine nichtlineare Kostenfunktionen ist das Finden einer Lösung NP-schwer.^[6]

Siehe auch

Literatur

Oliver Zlotowski: Design, Implementierung und Evaluierung von Netzwerkdatenstrukturen und Netzwerkalgorithmen zum Lösen des Minimum-Cost Flow Problems. Logos, Berlin 2010, ISBN 978-3-8325-2600-9.
L. Chen, R. Kyng, Y.P. Liu, R. Peng, M. Probst Gutenberg, S. Sachdeva: Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow. In: Communications of the ACM. Band 66, Nr. 12, 2023, S. 85–92, doi:10.1145/3610940.

Weblinks

Maximilian Probst Gutenberg: Der Algorithmus, der alle Erwartungen sprengte (Spektrum.de, 18. Dezember 2024)

Einzelnachweise

↑ Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. Springer; Auflage: 2., überarb. Aufl. 2009 (10. Juni 2009). ISBN 978-3642015793. Seite 169
↑ G. Monge. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année. 1781, S. 666–704.
↑ ^a ^b Ravindra K. Ahuja, Thomas Magnanti, James Orlin: Network flows : theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, N.J. 1993, ISBN 978-0-13-617549-0.
↑ Morton Klein: A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems. In: Management Science. Band 14, Nr. 3, 1. November 1967, ISSN 0025-1909, S. 205–220, doi:10.1287/mnsc.14.3.205 (informs.org [abgerufen am 5. September 2021]).
↑ M. Minoux: Solving integer minimum cost flows with separable convex cost objective polynomially. In: Netflow at Pisa (= Mathematical Programming Studies). Springer, Berlin, Heidelberg 1986, ISBN 978-3-642-00923-5, S. 237–239, doi:10.1007/bfb0121104.
↑ G. M. Guisewite, P. M. Pardalos: Minimum concave-cost network flow problems: Applications, complexity, and algorithms. In: Annals of Operations Research. Band 25, Nr. 1, 1. Dezember 1990, ISSN 1572-9338, S. 75–99, doi:10.1007/BF02283688.

[1] Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. Springer; Auflage: 2., überarb. Aufl. 2009 (10. Juni 2009). ISBN 978-3642015793. Seite 169

[Monge-2] G. Monge. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année. 1781, S. 666–704.

[:0-3] Ravindra K. Ahuja, Thomas Magnanti, James Orlin: Network flows : theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, N.J. 1993, ISBN 978-0-13-617549-0.

[4] Morton Klein: A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems. In: Management Science. Band 14, Nr. 3, 1. November 1967, ISSN 0025-1909, S. 205–220, doi:10.1287/mnsc.14.3.205 (informs.org [abgerufen am 5. September 2021]).

[5] M. Minoux: Solving integer minimum cost flows with separable convex cost objective polynomially. In: Netflow at Pisa (= Mathematical Programming Studies). Springer, Berlin, Heidelberg 1986, ISBN 978-3-642-00923-5, S. 237–239, doi:10.1007/bfb0121104.

[6] G. M. Guisewite, P. M. Pardalos: Minimum concave-cost network flow problems: Applications, complexity, and algorithms. In: Annals of Operations Research. Band 25, Nr. 1, 1. Dezember 1990, ISSN 1572-9338, S. 75–99, doi:10.1007/BF02283688.

[1]

[2]

[3]

[4]

[5]

[6]