Der kostenminimale Fluss nutzt nicht die teure Kante mit Kosten 3.

Das Min-Cost Flow Problem

Die Planung von Straßennetzen, Pipelines or Datennetzwerken sind die Motivation für die Flussprobleme genannte Klasse von Optimierungsproblem. Der charakterisierende Aspekt der zu planenden Netzwerke ist, dass eine Art Ressource durch die Kanten eines Netzwerks transportiert werden muss, welche jedoch nur eine bestimmte Menge an Fluss zulassen. Für manche der Optimierungsprobleme haben diese Transportkanten noch weitere Eigenschaften, welche es zum Beispiel motivieren, den Kanten Kosten zuzuweisen - beispielsweise Mautgebühren für die Nutzung von Straßen.

In solch einer Problemstellung ist es interessant, wie ein bestimmter Fluss mit minimalen Kosten durch das Netzwerk geschickt werden kann. Diese Problem wird das Min-Cost Flow Problem genannt.

Dieses Applet präsentiert den Cycle-Cancelling Algorithmus, welcher in einem gegebenen Netzwerk einen kostenminimalen Fluss berechnet.

Kostenminimale Flüsse

Das Berechnen von kostenminimalen Flüssen ist ein klassisches Optimierungsproblem, welches beispielsweise wie folgt motiviert werden kann: Finde für ein gegebenes Transportnetzwerk aus Straßen, deren Nutzung durch Kapazitäten eingeschränkt ist und zusätzlich mit Kosten belegt ist, den billigsten Weg, die maximal mögliche Anzahl an Gütern von Ort s zu Ort t zu transportieren.

Das zugehörige mathematische Modell benötigt die folgenden Informationen: Ein gerichteter Graph G(V,E) modelliert die Topologie des Netzwerks. Für jede Kante des Netzwerks ist eine Kapazitätsschranke bekannt, gegeben durch die Funktion u(e) | e ∈ E, und eine Kostenfunktion c(e), welche den Preis für das Versenden von einer Einheit des Guts über die Kante angibt. Zuletzt ist noch der Startknoten (auch Quelle genannt) und der Zielknoten (auch Senke genannt) nötig.

Die Lösung der Problemstellung ist ein Fluss f(e), welcher den Fluss auf jeder Kante angibt, der die Gesamtkosten minimiert. Die auf jeder Kante entstehenden Kosten sind hierbei einfach das Produkt der Kantenkosten und der Größe des Flusses auf der Kante. Die Lösung muss natürlich (damit es ein Fluss ist) auch den Anforderungen an einen Fluss genügen - über jede Kante darf maximal einen Fluss in Höhe u(e) fließen, und in jedem Knoten ausgenommen Quelle und Senke muss die Summe der eingehenden Flüsse gleich der der ausgehenden Flüsse sein.

Die Gesamtgröße des Flusses muss vor der Optimierung der Kosten festgesetzt werden. In dieser Anwendung betrachten wir die Fragestellung, wie man einen maximalen Fluss möglichst billig durch das Netzwerk schickt - das Min-Cost Max-Flow Problem.

Idee des Cycle Cancelling Algorithmus

Der Cycle Cancelling Algorithmus nutzt einen iterativen Ansatz für die Berechnung. Dazu startet er mit einem zulässigen Fluss der geforderten Größe (zum Beispiel durch einen Max-Flow Algorithmus wir Ford-Fulkerson berechnet). Im Anschluss reduziert er schrittweise die Kosten des Flusses, indem er den Fluss entlang von bestimmten Kreisen über billige Kanten schickt, ohne jedoch die Anforderungen an einen Fluss zu verletzen.

Mögliche Wege, wie man den Fluss umlegen kann, ergeben sich durch Betrachtung des Residualgraphen des aktuellen Flusses: Wenn man den Fluss entlang eines Kreises des Residualgraphen auf jeder Kante um den selben Betrag verändert, erhält man wieder einen zulässigen Fluss von Quelle zu Senke, welcher zudem immer noch die selbe Größe besitzt. Wenn die Summe der Kantenkosten auf dem Kreis negativ ist, wird eine Erhöhung des Flusses entlang des Kreises die Gesamtkosten des Flusses reduzieren und so die Lösung verbessern.

Negative Kreise in einem Graphen kann man beispielsweise über den Bellman-Ford Algorithmus finden. Nachdem man einen negativen Kreis gefunden hat, kann man so lange den Fluss entlang der Kreiskanten erhöhen, bis die erste Kante ihre Kapazitätsgrenze erreicht hat (d.h. saturiert ist). Hierdurch wird diese Kante aus dem Residualgraphen entfernt, und somit ebenso der Kreis. Da der Residualgraph aber natürlich immer noch andere Kreise enthalten kann, iteriert der Algorithmus und sucht über den Bellman-Ford Algorithmus nochmals nach negativen Kreisen.

Was nun?

Wie sieht der (Pseudo-)Code des Algorithmus aus?

Input: gerichteter Graph G=(V,E), Kapazitätsfunktion u(e), Kostenfunktion c(e), Quelle und Senke
Output: Min-Cost Max-Flow f(e)

BEGIN
  (* Initialisiere max. Fluss *)
  f = BERECHNE MAX FLOW()
  (* Main Loop *)
  WHILE negativer Kreis evtl. vorhanden DO
    KONSTRUIERE RESIDUALGRAPH G'(V,E') MIT KAPAZITÄTEN u'(e) 
    FÜHRE BELLMAN-FORD AUF G' VON SENKE AUS
    IF negativer Kreis gefunden
      IDENTIFIZERE Kreiskanten 
      Anpassung ← min(u'(e) | e ∈ Kreiskanten )
      FOR e ∈ Kreiskanten 
        f(e) += Anpassung 
END

Wie schnell ist der Algorithmus?

Literatur

Wo finde ich noch mehr Informationen zu Graphalgorithmen?

Ein letzter Hinweis zum Ziel und Inhalt dieser Seite und zu Zitationen