»Man darf nie an die ganze Straße auf einmal denken, verstehst du? Du musst nur an den nächsten Schritt denken, an den nächsten Atemzug, an den nächsten Besenstrich. Und immer wieder nur an den nächsten. Auf einmal merkst du, dass du Schritt für Schritt die ganze Straße gemacht hast.« Diese Lebensweisheit vermittelt der Straßenkehrer im berühmten Kinderbuch »Momo« von Michael Ende. Ein ähnliches Vorgehen hat nun einen neuen Algorithmus hervorgebracht, an dessen Machbarkeit viele Fachleute bisher zweifelten.

Fast 100 Jahre lang zerbrachen sich Mathematiker und Informatiker den Kopf, um das so genannte Min-Cost-Flow-Problem effizient zu lösen. Dabei geht es darum, den günstigsten Transportweg zu bestimmen, um innerhalb eines Netzwerks Waren von einem Punkt zu einem anderen zu bewegen. Lösungen für diese Aufgabe gab es, doch für große Netzwerke wuchs die nötige Rechenzeit stark an. Lange hoffte man auf einen Algorithmus, der das Problem in der gleichen Zeit bewältigt, wie es braucht, das Netzwerk überhaupt einzulesen. Doch alle Versuche scheiterten. Aber dann gelang uns im Frühjahr 2022 endlich der Durchbruch.

Ähnlich wie frühere Ansätze beginnt auch unserer mit einer suboptimalen Transportlösung, die dann schrittweise verbessert wird, bis der optimale Weg vorliegt. Was die Fachwelt überraschte: Unser Algorithmus macht pro Verbesserungsschritt nicht mehr, sondern weniger Fortschritte als bisherige Methoden. Wider Erwarten macht ihn genau das schneller, denn die winzigen Trippelschritte lassen sich effizient berechnen. Unser Ansatz ist damit nicht nur schneller als die bisherigen Programme, sondern er ist quasi die bestmögliche Lösung für das Min-Cost-Flow-Problem, sagte Aleksander Mądry vom Massachusetts Institute of Technology und OpenAI zu »Quanta Magazine«.

Netzwerkflüsse in der Praxis

Netzwerke lassen sich auf abstrakte Weise formulieren. Das ermöglicht es, Algorithmen wie unseren zumindest theoretisch auf viele verschiedene Probleme anzuwenden. Die Punkte eines Netzwerks werden als Knoten bezeichnet und die Verbindungen dazwischen als Kanten. Jede Kante hat eine Richtung, eine maximale Kapazität und kommt mit Kosten einher. Das Netzwerk kann somit beispielsweise ein Strom- oder Straßennetz beschreiben. Die Kapazität begrenzt, wie viel Ware einen Weg passieren kann – ab einer gewissen Anzahl an LKWs ist eine Straße beispielsweise ausgelastet. Die Kosten geben an, wie teuer es ist, eine Ware entlang dieser zu bewegen. Ziel des Min-Cost-Flow-Problems ist es, den Warenfluss zu berechnen, der eine bestimmte Menge von Waren von den Quellen zu den Senken des Netzwerks transportiert und dabei die Gesamtkosten minimiert.

Ein Stromnetz besteht beispielsweise aus vielen Leitungen, die jeweils eine bestimmte Kapazität haben, Strom zu transportieren. In diesem Netzwerk gibt es Stromerzeuger (Quellen) und Verbraucher (Senken). Um den Strom verlustarm zu verteilen, sucht der Algorithmus eine Transportstrecke mit möglichst kurzen Wegen. Ein anderes Anwendungsbeispiel ist der Güterverkehr. Eine Firma produziert Waren an mehreren Standorten (Quellen) und will diese dann kostengünstig an die Abnehmer (Senken) verteilen, etwa über Lastkraftwagen, die ein kompliziertes Straßennetz befahren. Je nach Route fallen unterschiedliche Kosten durch Spritverbrauch und Maut an.

Auf diese Weise lassen sich komplexe Transportprobleme modellieren und lösen, sei es in der Güterverteilung, dem Datenverkehr im Internet oder in der Finanzbranche. Auch bei der Herstellung von Mikrochips und der Entwicklung von Machine-Learning-Programmen kommen Algorithmen wie unsere zum Einsatz.

Optimale Warenflüsse durch schrittweise Verbesserung

In den 1930er Jahren erwähnte der sowjetische Forscher A. N. Tolstoi erstmals das Min-Cost-Flow-Problem. Damals untersuchte er das Schienennetz der Sowjetunion und versuchte, die Warenflüsse darüber zu verbessern. Dafür entwickelte er die erste Rechenvorschrift, die auch tatsächlich den optimalen Warenfluss liefert.

Seine Idee war folgende: Zunächst wählt man einen Warenfluss f, der die gewünschte Warenmenge transportiert und dabei die Kapazitäten aller Kanten einhält. Alles andere ist egal, f kann auch sehr hohe Kosten aufweisen. Die zentrale Überlegung ist, dass jeder andere Warenfluss f' in einem Netzwerk zum ursprünglichen f addiert werden kann. f' muss nicht zwingend Waren von Quelle zu Senke transportieren; sondern könnte auch nur eine Wareneinheit entlang eines kreisförmigen Wegs innerhalb des Netzwerks bewegen.

Um Tolstois Algorithmus zu verstehen, ist das Konzept des Residualnetzwerks wichtig. Dieses lässt sich wie folgt aus dem ursprünglichen Netzwerk ableiten: Für jede Kante von den Knoten A nach B mit Kosten k und Menge x im Warenfluss f fügt man dieselbe Kante von A nach B in das Residualnetzwerk ein. Dort hat es die gleichen Kosten k, aber eine um x reduzierte Kapazität k-x. Denn wenn bereits x Waren gesendet werden, ist die verbleibende Kapazität um x kleiner. Zusätzlich fügt man eine Kante von B nach A in das Residualnetzwerk ein, mit Kapazität x und Kosten -k: Wenn man Ware von B nach A sendet, wird der bestehende Warenfluss von A nach B effektiv gelöscht, was die Kosten um k pro Wareneinheit senkt. Man kann aber nur so viel Ware zurücksenden, wie ursprünglich im Umlauf war. Am Ende werden alle Kanten mit einer Kapazität von null gelöscht.

Tolstois Algorithmus startet mit einem Warenfluss f, der die richtige Warenmenge von Quelle zu Senke sendet (mit suboptimalen Kosten). Dann wählt das Programm einen kreisförmigen Weg aus dem Residualnetzwerk mit negativen Kosten und sendet möglichst viel Ware entlang dieses Wegs – so viel, wie die Kapazitäten im Residualnetzwerk zulassen. Dieser Warenfluss wird dann zu f addiert. Der Algorithmus erzeugt anschließend das neue Residualnetzwerk und wiederholt den Vorgang. Wenn kein Kreis mit negativen Kosten mehr existiert, endet der Algorithmus.

Anders als bei vielen anderen Netzwerkproblemen, deren optimale Lösung sich auf Anhieb berechnen lässt, fußen noch heute alle Algorithmen für das Min-Cost-Flow-Problem auf der schrittweisen Verbesserung einer suboptimalen Lösung.

Tolstois Methode liefert zwar stets einen optimalen Warenfluss, das kann aber teilweise extrem lange dauern. Denn die Anzahl der Verbesserungsschritte ist nur durch die Gesamtkosten eines optimalen Warenflusses begrenzt. In Tolstois Beispiel mit dem sowjetischen Schienennetz besitzt das Netzwerk bloß 155 Kanten. Doch selbst für dieses – im Vergleich mit vielen Anwendungen – kleine Netzwerk betrugen die Gesamtkosten 395 052 Einheiten. Das heißt, man könnte bis zu 395 052 Rechenschritte benötigen, bis man bei der optimalen Lösung angelangt ist.

Glücklicherweise konnte Tolstoi den schlimmsten Fall (nämlich die 395 052 Rechenschritte) durch geschicktes, händisches Auswählen der negativen Kreise abwenden. Sein Algorithmus endete nach nur zehn Schritten. Weil moderne Netzwerke aber oft aus mehreren Millionen (etwa das Straßennetz in Europa) oder gar Milliarden Kanten bestehen, ist eine solche Herangehensweise hoffnungslos.

Deshalb wurde der von Tolstoi vorgegebene Weg automatisiert. Forschende suchten nach Regeln, um gezielt die Kreise auszuwählen, die mit möglichst wenigen Verbesserungsschritten große Verbesserungen bringen. Dabei konzentrierten sie sich zunächst auf ein vereinfachtes Problem, das die Kostenminimierung ignoriert. In dieser Version gilt es herauszufinden, wie viel Ware sich von Quelle zu Senke senden lässt – ungeachtet der Kosten. Ziel ist die Berechnung des »maximalen Warenflusses«.

Der maximale Warenfluss

Getrieben wurde diese Entwicklung zuerst durch die US Air Force in den 1950er Jahren, die sich wie Tolstoi für das sowjetische Schienennetz interessierte, allerdings aus ganz anderen Gründen. Denn der maximale Warenfluss offenbart die schwächste Stelle eines Netzwerks – und damit jene Verbindung, die den Warenfluss von Quelle zu Senke stoppen kann. In umfangreichen Berechnungen ermittelte die US Air Force den besten Weg, um das sowjetische Schienennetzwerk von strategischen Zielen abzuschneiden.

Die Luftstreitkraft wandte sich dabei an die renommierten Mathematiker Lester Ford und Delbert Fulkerson, die das Problem in der Fachwelt verbreiteten. Wegen der vielen möglichen Anwendungen stieg es schnell zu einem zentralen Forschungsthema der Algorithmik auf. Bis in die 1990er Jahre wurde es intensiv erforscht; immer wieder entstanden neue Algorithmen, die das Feld nachhaltig prägten. Einige dieser Ergebnisse werden bis heute standardmäßig an Universitäten gelehrt.

Doch selbst der damals beste Algorithmus war nicht sonderlich effizient: Wenn ein Netzwerk aus m Kanten besteht, benötigen die Methoden bis zu √m Verbesserungsschritte, um den maximalen Warenfluss zu berechnen. Für das komplexere Min-Cost-Flow-Problem war die Zahl sogar deutlich höher.

Das Rennen um den größten Fortschritt

Die Informatiker Andrew Goldberg und Robert Tarjan entwickelten 1990 den bis dahin effizientesten Algorithmus für das Min-Cost-Flow-Problem. Dieser wählt den Kreis mit den niedrigsten – den höchsten negativen – Durchschnittskosten als Verbesserungsschritt. Die Durchschnittskosten eines Kreises entsprechen den Kosten geteilt durch die Länge, also die Anzahl der Kanten. Damit bewiesen die Forscher, dass die Verbesserungsschritte nur polynomiell (und nicht etwa exponentiell) mit der Kantenzahl m wachsen, und dass man den Kreis mit den geringsten Durchschnittskosten effizient im Residualnetzwerk finden kann.

Obwohl sehr viele unterschiedliche Algorithmen entwickelt wurden – mit teilweise hochkomplexen Regeln für das Auswählen der Kreise –, erreichte keiner das angestrebte Ziel: die Verbesserungsschritte unabhängig von der Anzahl an Kanten m und den Kosten der optimalen Lösung zu machen. Damit blieb der Traum einer möglichst effizienten Methode unerfüllt.

Die Abkehr von den Kreisen

Nach etwa 80 Jahren, in denen sich die Fachwelt darauf konzentriert hatte, den nächsten Kreis auszuwählen, schlugen die Informatiker Daniel Spielman und Samuel Daitch im Jahr 2008 einen völlig neuen Ansatz vor, der die Anzahl von Verbesserungsschritten durch √m begrenzt – und das, obwohl der Algorithmus das Min-Cost-Flow-Problem löst. Er braucht also nur in etwa so viele Schritte wie die Programme für das einfachere maximale Warenflussproblem.

Spielman und Daitch nutzten dafür die so genannte Interior-Point-Methode (kurz: IPM, ein bekanntes Werkzeug der Optimierung), die eine suboptimale Lösung auch ohne Kreise verbessert. Inspiriert ist das Ganze von elektrischen Strömen. In diesem Fall übernehmen die Elektronen die Rolle der Waren und Widerstände der Leitungen repräsentieren die Kapazitäten. Da Elektronen immer den Weg des geringsten Widerstands wählen (wobei sie sich auch gegenseitig als Widerstände wahrnehmen), bieten sie einen guten Ausgangspunkt, um das Min-Cost-Flow-Problem zu lösen.

Spielman und Daitch wandelten hierfür die Preisfunktion in Spannungsquellen und Verbraucher um und berechneten dann den elektrischen Stromfluss für die Elektronen durch das Netzwerk. Sie justierten dabei die Spannungsquellen und -senken sowie die Widerstände so, dass der Schaltkreis zu ihrem Netzwerkproblem passte. Der Stromkreislauf wird somit zu einer komplizierten Verbindung vieler Kreise, so dass bei jedem Rechenschritt das gesamte Netzwerk nachjustiert wird – und nicht nur ein einzelner Bereich, wie es bei bisherigen Ansätzen der Fall war. Daher ist diese Methode deutlich effektiver, als den besten Kreis auszuwählen.

Erstaunlich ist, dass die elektrischen Ströme, die den Fluss schrittweise verbessern, nicht im Residualnetzwerk, sondern im ursprünglichen Netzwerk gefunden werden. In diesem besitzen die Kanten jedoch keine Richtung mehr, wodurch der elektrische Strom zur einen oder anderen Seite fließen kann. Das hat allerdings einen Nachteil. Das IPM erzeugt zwei komplizierte Funktionen statt nur einer. Nach jedem Verbesserungsschritt erhalten die Kanten einen neuen Preis und einen neuen Widerstandswert. Das IPM sucht dann nach einem Warenfluss, der den höchsten negativen Preis geteilt durch den Widerstand des Flusses erzielt.

Dennoch brachte die Abkehr vom Residualnetzwerk den entscheidenden Vorteil. Denn durch einen vorigen Geniestreich von Spielman und seinem damaligen Mitarbeiter Shang-Hua Teng ist die Berechnungsdauer des elektrischen Stromflusses (was einem Verbesserungsschritt entspricht) in einem ungerichteten Netzwerk ungefähr so lang, wie die nötige Zeit, um das Netzwerk einzulesen. Für diesen Durchbruch hatten sie 2008 den Gödel-Preis erhalten, eine der höchsten Auszeichnungen in der Algorithmik. Diese Methode ließ sich mit dem Algorithmus für elektrische Stromflüsse verbinden. Das ergab einen neuen Ansatz für das Min-Cost-Flow-Problem, der deutlich schneller war als alle bisherigen Lösungen. Doch die gesamte Berechnungsdauer skalierte immer noch mit der Anzahl an Kanten.

»Es gab keinen guten Grund zu glauben, dass wir so einen Algorithmus finden können«Daniel Spielman, Informatiker

Es folgte eine neue Epoche des Enthusiasmus. Sie belebte die Forschung um das Problem wieder und brachte viele neue Einsichten. Schnell fanden sich erste Verbesserungen, die verschiedene Varianten des Verfahrens beschleunigten. Doch das Ziel, die Anzahl der Verbesserungsschritte auf ein Minimum zu senken, wurde nicht erreicht. Es kamen Zweifel auf, ob es überhaupt gelingen könnte. »Es gab keinen guten Grund zu glauben, dass wir so einen Algorithmus finden können«, äußerte sich Spielman später gegenüber »Quanta Magazine«.

Die Rückkehr zu den Kreisen

2022 gelang fünf Kollegen und mir schließlich der entscheidende Durchbruch. Zunächst entwickelten wir ein neues IPM, das nicht wie bei Spielman in jedem Schritt die elektrischen Stromflüsse berechnet. Stattdessen bestimmt es einen Kreis mit dem niedrigsten Durchschnittspreis. Das IPM erzeugt also wieder zwei Funktionen, eine Preis- und eine Längenfunktion, anders als bei Spielman und Daitch, wo eine Widerstandsfunktion generiert wurde. Es sucht dann nach dem Kreis mit den geringsten Durchschnittspreis im Netzwerk.

Obwohl für jeden Verbesserungsschritt ein ähnliches Problem wie beim Algorithmus von Goldberg und Tarjan gelöst werden muss, unterscheiden sich die dazugehörigen Aufgaben grundlegend. Das IPM muss den niedrigsten Durchschnittspreis in einem ungerichteten Netzwerk finden, was deutlich einfacher ist als in gerichteten Netzwerken.

Die Anzahl der Verbesserungsschritte beträgt ungefähr m: deutlich mehr als bei den vorher effizientesten Algorithmen, aber weniger als bei der Methode von Goldberg und Tarjan. Das Entscheidende ist aber, dass sich die Preis- und Längenfunktion nur für extrem wenige Kanten ändert. Das ist bei Residualnetzwerken völlig anders, da sich dort in jedem Schritt um bis zu m Kanten ändern können. Wir erkannten, dass diese Stabilität eine deutlich effizientere Berechnung des nächsten Kreises ermöglicht. Anstatt wie bisher in jedem Schritt alle Kanten zu untersuchen, kann man nur die Kanten betrachten, auf denen sich die Preis- oder Längenfunktion geändert haben.

Das war ein echter Gamechanger: Statt jedes Mal das Netzwerk komplett neu auszuwerten, berechnet der Algorithmus den nächsten Kreis quasi ohne Aufwand. Somit können die m Verbesserungsschritte in der Zeit gelöst werden, die benötigt wird, um das Netzwerk einzulesen. Während sich der Algorithmus in vielen kleinen Schritten vorarbeitet, erreicht er in Windeseile sein Ziel – ganz so, wie der Straßenkehrer in der Geschichte »Momo« die Straße säubert.

Praktische Anwendungen

Anfangs war der neue Algorithmus vor allem ein mathematischer Durchbruch. Für einen direkten Einsatz in der Praxis sind zu viele Komponenten involviert. »In den nächsten Jahren werden Algorithmiker höchstwahrscheinlich Wege finden, den Algorithmus praktisch und sogar noch etwas schneller zu machen«, sagte im Jahr 2022 Richard Peng von der Carnegie Mellon University, der am Design des neuen Algorithmus beteiligt war. Und er sollte Recht behalten: Bereits ein Jahr später trafen sich führende Experten für ein Forschungssemester am Simons Institute in Berkeley, um den Algorithmus besser zu verstehen. Heraus kamen gleich zwei neue Versionen, die schneller waren und breitere Anwendungen ermöglichen.

»Das ist nicht das Ende der Geschichte«, prophezeite Nikhil Srivastava vom Simons Institute. Auch der ursprüngliche Algorithmus von Spielman und Teng war anfangs extrem komplex. Die Beschreibung und Analyse umfasste mehr als 140 Seiten. Doch nach 20 Jahren intensiver Forschung lässt er sich auf weniger als 20 Seiten erklären. Jetzt lässt er sich effizienter implementieren. Wie Srivastava feststellte muss »dasselbe nun für das Min-Cost-Flow-Problem passieren«.