Mathematik: Die Optimierung der Welt

Kunden, die dieses Produkt gekauft haben, haben sich auch für folgende Produkte interessiert...“ Klar, denn wer ein Babybett gekauft hat, der interessiert sich wohl auch für Babyspielzeug. Und wer in der Onlinevideothek zuletzt „Vom Winde verweht“ und „Der englische Patient“ ausgeliehen hat, dem könnte auch „Sinn und Sinnlichkeit“ gefallen. Aber könnte er auch „Drei Engel für Charlie“ oder sogar „Kill Bill“ mögen?

Eine der größten Onlinevideotheken, die amerikanische Firma Netflix, kämpfte mit genau dieser Frage. 2006 lobte sie daher einen Preis von einer Million Dollar aus. Ziel war die Entwicklung eines mathematischen Verfahrens, das den Geschmack von Kunden deutlich besser vorhersagte als „Cinematch“, das bisherige Verfahren. Kunden bei Netflix können Filme mit einem bis fünf Sternen bewerten und auf der Basis dieser Benotung werden dann Vorschläge gemacht. Der durchschnittliche Kunde hat allerdings nur etwa jeden fünfhundertsten Film im Netflix-Angebot mit Sternen bedacht – und das noch nicht einmal zuverlässig, wie die Analyse der Mathematiker zeigte. Wie viele Sterne vergeben werden, hängt offenkundig auch von der Tagesform des Kunden ab und davon, ob die Bewertung direkt nach dem Sehen des Films oder Monate später abgegeben wird.

Aus derart dünnen, unsicheren Daten gute Vorhersagen zu basteln, ist eine klassische Aufgabe für ein noch junges, aber rasant wachsendes Teilgebiet der Mathematik: die Optimierung. Forscher in diesem Bereich interessieren sich ebenso dafür, einen Stundenplan zu verbessern wie den Schiffsverkehr zu beschleunigen. Weite Teile dieses Feldes, etwa die kombinatorische Optimierung, die sich mit dem Finden von kürzesten Wegen auf Landkarten oder mit Suchalgorithmen in digitalen Daten befasst, sind erst im ausgehenden Zweiten Weltkrieg entstanden.

Alle drei Jahre treffen sich die Forscher zu einer riesigen Konferenz. Ab Montag ist die Technische Universität Berlin (TU) Gastgeber für das ISMP, das International Symposium on Mathematical Programming. Mit Programmieren haben die meisten Teilnehmer dabei nur wenig am Hut. „Der Begriff stammt aus der Anfangszeit der mathematischen Optimierung nach dem Zweiten Weltkrieg, als man auf der Suche nach einem coolen Titel war“, erklärt Martin Skutella. Der Mathematiker der TU Berlin hat die Tagung organisiert. „Eigentlich sind damit Modelle und Algorithmen gemeint, also mathematische Handlungsanweisungen, mit denen man Lösungen finden kann.“

Das „Netflix-Problem“ faszinierte die Optimierer. Insgesamt arbeiteten laut Unternehmen mehr als 50 000 Forscher daran – und tatsächlich konnten sie die Vorhersagekraft um mehr als zehn Prozent verbessern. Sie entwickelten ein trickreiches Verfahren, das aus den gegebenen Bewertungen etwa 50 Kriterien errechnet, nach denen die Filme eingeteilt werden können. Zum Teil kann man diese in Worte fassen („ernst“ vs. „unterhaltsam“), oft spiegeln sie sich aber auch nur in einer Reihe von Zahlen wider. Eine der Ideen: Um vorherzusagen, wie ein Nutzer einen unbekannten Film finden könnte, betrachtet man nur, wie er Filme bewertet hat, die ähnlichen Kriterien genügen.

Die Methoden, mit denen in der Optimierung gearbeitet werden, können ganz unterschiedlich sein. Manche Verfahren stellen in vieldimensionalen Kurven den Anstieg in jedem Punkt fest, um so Täler oder Gipfel zu finden. Einige Probleme lassen sich auch in kleinere Teilprobleme zerlegen. Diese werden dann jedes für sich gelöst und hinterher zur Gesamtlösung zusammengesetzt. Bei allen Unterschieden eint die Optimierung aber eines: Wie kaum ein anderes Teilgebiet der Mathematik ist man hier an der Anwendung interessiert. Man könnte sagen: Optimierer stellen mathematisches Werkzeug her, mit dem Probleme bearbeitet und gelöst werden können – im besten Falle optimal.

Tatsächlich hat viel Wissen aus der Optimierung Einzug in das Alltagsleben gehalten, von automatisch generierten Kaufempfehlungen in Internetshops bis zur Stunden- und Raumplanung in Schulen. Auch die Mathematiker selbst standen vor einem solchen Optimierungsproblem, als sie ihre rund 1700 Vorträge der Tagung auf die Räume in der TU zu verteilen hatten. „Scheduling“ nennen sie so etwas, nach dem englischen Wort für Stundenplan (schedule). Und wie man Stundenpläne bastelt, die mit möglichst wenig Räumen und Raumwechseln auskommen, ist traditionell ein Thema für Optimierer. Kaum ein Dienstplan wird heute ohne Computer erstellt und das funktioniert nur deshalb, weil in der Software jede Menge mathematische Tricks stecken. Tricks, wie sie die Optimierer auf dem ISMP austauschen.

Dass man für ein Handytelefonat keine Unsummen bezahlen muss, beruht maßgeblich darauf, dass die Anbieter nur wenige der teuren Funkfrequenzen verwenden müssen, weil sie die Frequenzen dynamisch unter den Handynutzern aufteilen können – mithilfe von mathematischer Optimierung. Jedes Handy bekommt für ein Telefonat eine Frequenz zugewiesen, auf der es sendet, wobei zwei benachbarte Handys unterschiedliche Frequenzen brauchen, um sich nicht ins Gehege zu kommen. Die Frage ist: Wer bekommt welche Frequenz, so dass insgesamt nur möglichst wenige Frequenzen verwendet werden? Und einer der Vorträge auf der diesjährigen Tagung befasst sich damit, wie ein Anbieter für Bezahlfernsehen im Internet die Filme auf seine Server verteilen muss, so dass die Filme immer gerade da zur Verfügung stehen, wo sie gebraucht werden, und nicht auf langen Umwegen durch das Internet geschleust werden müssen.

Machten auf früheren Konferenzen solche Optimierungsaufgaben aus Internetwirtschaft und Telekommunikation noch den Löwenanteil aus, tritt 2012 ein anderer Bereich in den Vordergrund: die Energiewirtschaft. Die verteilte Stromerzeugung in Windkraft- und Photovoltaik-Anlagen stellt die Branche vor neue Herausforderungen. Welche Kraftwerke aktiviert man wann und wo, um die Netze nicht zu überlasten, aber überall den Strombedarf zu decken? Einer der Vorträge befasst sich zum Beispiel damit, wie in Brasilien Ausfälle bei Windkraftanlagen durch Verträge mit einem Wasserkraftanbieter ausgeglichen werden.

Besonders reizt die Optimierer dabei, dass bei vielen dieser Probleme der Zufall gehörig mitmischt: Man kann nur ungefähr vorhersagen, wo wann wie viel Strom produziert und wo er benötigt wird. Selbst Routenplaner und Navigationsgeräte - ebenfalls ein aktuelles Thema für die Optimierer - müssen inzwischen mit solch wackeliger Datenbasis umgehen. Längst sind die Zeiten vorbei, in denen das Navi nur die schnellste Route innerhalb von wenigen Sekunden berechnen musste. Heute soll die Routenplanung auch mögliche Staus einbeziehen oder die Vorliebe des Nutzers für Pflasterstraßen oder schönen Ausblick. Manche Hersteller schließen daher Verträge mit Taxi-Unternehmen; die Taxis melden dem Navigationsgerätehersteller, wo sie gerade stehen oder fahren. Der schätzt dann mit den Daten ab, wo gerade viel los sein könnte und teilt das den Navis mit – die das bei der Routenplanung berücksichtigen.

Die Berechnung der kürzesten Route im Navigationssystem lässt die Herzen der Optimierer höher schlagen. Aber kann man auch eine kürzeste Route berechnen, die durch alle Städte auf einer gegebenen Landkarte führt und jede Stadt nur einmal besucht? Für diese Frage gibt es viel weniger Anwendungen: Das „Problem des Handlungsreisenden“, der alle Städte genau einmal besuchen muss und dabei keine Straße zweimal beschreiten darf, ist ein Dauerbrenner der Theorie. Es begleitet die Optimierungstheorie wie die Drosophila die Molekularbiologie: Seit den 40er Jahren zerbrechen sich Theoretiker die Köpfe über das Travelling Salesman Problem, von Eingeweihten kurz TSP genannt.

Einen der ersten Erfolge vermeldete das amerikanische Magazin „Newsweek“ am 26. Juli 1954, da war die kombinatorische Optimierung gerade erst geboren: Drei Mathematiker hatten die kürzeste Rundroute durch 49 amerikanische Städte bestimmt. Die Schwierigkeit liegt darin, dass der Reisende bei 49 Städten zwischen etwa 6 x 1062 Routen wählen kann – weit mehr als alle Wassermoleküle in allen Weltmeeren zusammen.

Heute ist man so weit, die kürzeste Route durch 1 904 711 Städte auf der Erde anzugehen. Dafür ist zwar bisher noch keine optimale Lösung bekannt; die beste bekannte Route weicht allerdings höchstens 0,0477 Prozent vom Optimum ab. Schon diese Angabe werten die Optimierer als großen Erfolg, denn tatsächlich ist es in der Praxis oft gar nicht so entscheidend, ob eine Lösung optimal ist oder nicht – wichtig ist, zu wissen, wie weit man neben dem Optimum liegt.

Auch an den Erfolgen beim TSP kann man sehen, dass die Algorithmen immer besser werden. Bob Bixby, amerikanischer Mathematiker und Mitbegründer zweier Softwarefirmen, rechnete das einmal anhand eines Problems aus der Wirtschaft vor: Auf einem normalen PC hätte es 1997 1,5 Stunden gedauert, das Problem zu lösen. Nur fünf Jahre später schaffte man es in 87 Sekunden – auf demselben PC. Die Beschleunigung um einen Faktor von etwa 43 500 kam ausschließlich von besserer Mathematik in der Optimierungssoftware. Sie stellte selbst den rasanten Anstieg in der Leistungsfähigkeit von Prozessoren in den Schatten.

Der Autor ist Mathematiker an der Freien Universität Berlin.

Andreas Loos