Martin Grötschel: Die Geometrie harter Probleme

Im Jahr 1982 ging der Fulkerson-Preis —die anspruchsvollste Auszeichnung der diskreten Mathematik, gemeinsam vergeben von der American Mathematical Society und der Mathematical Optimization Society— an Arbeiten zur Ellipsoidmethode. Das dahinterstehende Ergebnis, das Martin Grötschel mit László Lovász und Alexander Schrijver entwickelte, etablierte etwas, das bis heute bestimmt, wie Theoretiker über kombinatorische Optimierung denken: dass für eine sehr breite Klasse von Problemen die Fähigkeit zur Separation —zu beantworten, ob ein Punkt innerhalb einer Menge liegt, und wenn nicht, eine trennende Hyperebene zu erzeugen— rechnerisch äquivalent dazu ist, über diese Menge zu optimieren. Optimierung und Separation sind die gleiche Schwierigkeit in verschiedenen Gewändern.

Von Schwelm nach Bonn

Grötschel wurde am 10. September 1948 in Schwelm geboren, einer kleinen Industriestadt in Nordrhein-Westfalen. Ab 1969 studierte er Mathematik mit Nebenfach Wirtschaftswissenschaften an der Universität Bochum, machte 1973 sein Diplom und wechselte dann als wissenschaftlicher Mitarbeiter an die Universität Bonn, wo er neun Jahre blieb. Sein Doktortitel folgte 1977 bei Bernhard Korte, einem der Begründer der deutschen diskreten Optimierung; seine Habilitation in Operations Research schloss sich 1981 in Bonn an.

Die Doktorarbeit wandte sich direkt dem berühmtesten schwierigen Problem der Disziplin zu. Grötschel brachte die Schnittebenenverfahren für das Problem des Handlungsreisenden voran —der Ansatz, bei dem man ein hartes kombinatorisches Problem in ein kontinuierliches entspannt, die einfache Version löst und dann Ungleichungen hinzufügt, die die durch die Entspannung erzeugten gebrochenen Antworten abschneiden, bis die Lösung ganzzahlig ist. Die Technik steht und fällt mit dem Wissen, welche Ungleichungen hinzuzufügen sind, und die Suche danach, die polyedrische Kombinatorik, wurde zum Mittelpunkt seiner Karriere: das Verständnis der Geometrie der konvexen Hülle der zulässigen Lösungen eines Problems, da diese Geometrie der Ort ist, an dem die Schwierigkeit tatsächlich liegt.

Ellipsoide

Die Ellipsoidmethode kam 1979 als erster Beweis dafür, dass lineare Programmierung in Polynomialzeit lösbar ist, in den Westen. Sie war und ist in der Praxis hoffnungslos —viel langsamer als das Simplex-Verfahren, das sie theoretisch dominierte. Was Grötschel, Lovász und Schrijver erkannten, war, dass ihre wahre Stärke nicht als Algorithmus, sondern als Beweismittel lag.

Da die Ellipsoidmethode nur ein Separationsorakel anstelle einer expliziten Liste von Beschränkungen benötigt, kann sie über Polyeder mit exponentiell vielen Facetten optimieren, vorausgesetzt, man kann eine verletzte Beschränkung effizient erkennen. Diese Beobachtung verwandelte eine Reihe offener Fragen auf einen Schlag in gelöste: Ganze Familien kombinatorischer Probleme erwiesen sich als in Polynomialzeit lösbar, ohne dass jemand einen direkten Algorithmus für sie konstruieren musste. Der Rahmen wurde vollständig in der Monographie Geometric Algorithms and Combinatorial Optimization dargelegt, die zu einem der Standardwerke des Feldes wurde. Der Fulkerson-Preis 1982 würdigte die Arbeit; 1991 folgte der George B. Dantzig Prize.

Berlin

Grötschel hatte von 1982 bis 1991 den Lehrstuhl für Angewandte Mathematik an der Universität Augsburg inne, wechselte dann nach Berlin, wo er den Rest seines Berufslebens verbrachte. 1991 wurde er ordentlicher Professor für Informationstechnik an der Technischen Universität Berlin und im selben Jahr Vizepräsident des Zuse-Instituts Berlin; 2012 übernahm er die Präsidentschaft des ZIB und behielt sie bis 2015. Von 2015 bis 2020 amtierte er als Präsident der Berlin-Brandenburgischen Akademie der Wissenschaften, und seit 2011 ist er Distinguished Affiliated Professor an der Technischen Universität München.

Die Berliner Jahrzehnte verlagerten seinen Schwerpunkt auf Anwendungen, ohne die Theorie aufzugeben. Er war Mitbegründer und Vorsitzender des DFG-Forschungszentrums Matheon, einer Einrichtung, die auf der Prämisse aufbaute, dass industrielle und infrastrukturelle Probleme wirklich neue Mathematik generieren, statt nur alte zu konsumieren. Seine angewandte Arbeit erstreckt sich auf Produktionsplanung, Zeitplanung im öffentlichen Verkehr, Energiesysteme und Logistik —Bereiche, in denen ein paar Prozent Verbesserung in einem kombinatorischen Zeitplan viel Geld und eine messbare Menge an Kohlenstoff wert sind.

Er war zudem ein ungewöhnlich aktiver Institutionenbauer. Er fungierte 1993–94 als Präsident der Deutschen Mathematiker-Vereinigung, von 2007 bis 2014 als Generalsekretär der International Mathematical Union und von 2011 bis 2015 als Vorsitzender der Einstein Stiftung Berlin. Er war Mitherausgeber des Handbook of Combinatorics. Die Preise häuften sich: der Karl-Heinz-Beckurts-Preis 1990, der Gottfried-Wilhelm-Leibniz-Preis —Deutschlands wertvollste Forschungsauszeichnung— 1995, die EURO Gold Medal 2004, der John von Neumann Theory Prize 2006, SIAM Fellowship und der SIAM Distinguished Service Prize um 2009–10. Er hält Ehrendoktorwürden von vier Universitäten und gehört sieben Akademien an, darunter die US National Academy of Engineering, die Leopoldina, acatech, Academia Europaea und die Chinesische Akademie der Wissenschaften.

Warum Martin als Genie bezeichnet wird

Das Wort wird in seinem Fachbereich nicht für ihn verwendet, und die ehrliche Beschreibung ist anders und nützlicher: Grötschel ist ein Mathematiker ersten Ranges, dessen Auszeichnung durch externe Urteile ungewöhnlich gut dokumentiert ist. Drei der höchsten Auszeichnungen in der Optimierung —Fulkerson, Dantzig, von Neumann— plus der Leibniz-Preis und die Mitgliedschaft in den amerikanischen, deutschen und chinesischen nationalen Akademien bilden eine Spur technischer Exzellenz, die nur sehr wenige arbeitende Mathematiker vorweisen können.

Die spezifische Qualität ist eher architektonisch als auffällig. Die Einsicht der Ellipsoidmethode ist das klarste Beispiel: Die Leistung bestand nicht darin, einen neuen Algorithmus zu erfinden, sondern zu erkennen, dass ein existierender, praktisch nutzloser Algorithmus eine allgemeine Äquivalenz kodierte, und aus dieser Äquivalenz eine Maschine zur Lösung von Fragen für ein ganzes Fachgebiet zu extrahieren. Das ist eine besondere Art von Geist —einer, der auf ein Werkzeug schaut und ein Theorem sieht. Dasselbe Instinkt zeigt sich im polyedrischen Programm, wo der Schritt darin besteht, eine diskrete Suche in eine Frage über die Form eines konvexen Körpers zu verwandeln, und wieder bei Matheon, wo der Schritt darin besteht, ein industrielles Zeitplanungsproblem als Quelle von Mathematik statt als deren Anwendung zu behandeln.

Der Gegenfall ist unkompliziert und erwähnenswert. Grötschels zentrale Ergebnisse werden mit Mitarbeitern geteilt, hauptsächlich Lovász und Schrijver, und es würde den Sachverhalt falsch darstellen, die Separation-Optimierung-Äquivalenz allein ihm zuzuschreiben. Sein Ruhm ist auf sein Spezialgebiet beschränkt; außerhalb der kombinatorischen Optimierung und des Operations Research ist er im Wesentlichen unbekannt, und kein Ergebnis trägt seinen Namen in den allgemeinen mathematischen Wortschatz. Ein beträchtlicher Teil seiner späteren Karriere floss in Verwaltung, Fördergremien und Gesellschaftspräsidentschaften statt in Beweise. Was die Aufzeichnungen stützen, ist kein gefeiertes Genie, sondern etwas präziser Wertvolles: eine Karriere erstklassiger Ergebnisse, ein Rahmen, den das Fachgebiet noch heute täglich nutzt, und ein institutionelles Vermächtnis in Berlin, das jedes individuelle Theorem überdauert.

Vermächtnis

Die Separation-Optimierung-Äquivalenz ist heute Standardausrüstung, die jedem Doktoranden in diesem Bereich gelehrt wird und immer dann herangezogen wird, wenn eine neue Klasse von Entspannungen vorgeschlagen wird. Der polyedrische Ansatz, den er mitbegründete, liegt den kommerziellen Ganzzahl-Programmierung-Solvern zugrunde, die Flugzeuge leiten, Züge planen und Stromnetze auslegen. Und ZIB, Matheon und die Berliner Optimierungsschule sind institutionelle Fakten vor Ort, besetzt mit Leuten, die von ihm lernten, dass ein hartes praktisches Problem und ein tiefes mathematisches Problem oft dasselbe Objekt sind, betrachtet aus zwei Seiten.