Mit Nummer 9 zum renommierten SIGEST Preis!

Hinweis zur Verwendung von Bildmaterial: Die Verwendung des Bildmaterials zur Pressemitteilung ist bei Nennung der Quelle vergütungsfrei gestattet. Das Bildmaterial darf nur in Zusammenhang mit dem Inhalt dieser Pressemitteilung verwendet werden. Falls Sie das Bild in höherer Auflösung benötigen oder Rückfragen zur Weiterverwendung haben, wenden Sie sich bitte direkt an die Pressestelle, die es veröffentlicht hat.

Menge der zulässigen Lösungen eines linearen Programms (links), einer logarithmischen Deformation (Mitte) und dem tropischen Grenzwert (rechts). | Quelle: M. Joswig/T. Brysiewi (MPI-MiS) | Copyright: © M. Joswig / T. Brysiewicz (MPI Mathematik in den Naturwissenschaften) | Download

Die von Michael Joswig gemeinsam mit seinen Kollegen verfasste Arbeit leistet einen
maßgeblichen Beitrag für das Verständnis des neunten Problems auf der sogenannten
Smale-Liste. Der Fields-Medaillist Steven Smale hatte im Jahr 2000 eine Liste von 18
mathematischen Problemen zusammengestellt, die er für wegweisend für die Entwicklung
der Mathematik des 21. Jahrhunderts hielt. Beim Problem mit der Nummer 9 geht es um die
Frage, wie schnell sich lineare Programme genau lösen lassen. Der ausgezeichnete Artikel
erschien nun in einer erweiterten Version in SIAM Review unter der Rubrik SIGEST, für welche pro Quartal ein herausragender Beitrag ausgewählt wird.

Lineare Programme sind zentral für die Lösung komplexer Optimierungsprobleme, sowohl in
der mathematischen Theorie als auch in der wirtschaftlichen Praxis. Beispiele finden sich bei
der Modellierung von Produktionsprozessen oder in der Logistik. Die Herausforderung
besteht darin, auch mit hunderttausenden Variablen und Nebenbedingungen schnell genug
zum Ziel zu gelangen. Michael Joswig konstruiert zur Veranschaulichung folgendes Beispiel
aus der Alltagswelt: „Im Supermarkt möchte ich von n verschiedenen Lebensmitteln jeweils
so viel kaufen, dass mein Tagesbedarf für verschiedene Nährstoffe gedeckt wird. Hierfür
möchte ich so wenig wie möglich investieren. Dieses Optimierungsproblem ist ein lineares
Programm mit n Variablen und m Nebenbedingungen.“

Wegen ihres erheblichen Nutzens sind Algorithmen zur Lösung linearer Programme seit mehr
als 70 Jahren ein intensiv beforschtes Thema an der Grenze zwischen Mathematik und
Informatik. Lineare Programme werden zu jedem Zeitpunkt mindestens millionenfach auf der
Welt gelöst. Der Analyse von Laufzeiten von Algorithmen, beispielsweise implementiert in
Computerprogrammen, kommt eine besondere Bedeutung zu, denn sie garantieren,
benötigte Ergebnisse mit möglichst minimalem Zeitaufwand zu erzielen.

In dieser langen Zeit gab es eine ganze Reihe von bedeutenden Fortschritten. Dennoch
bleibt eine grundsätzliche Frage bis heute offen, die Smale in seinem neunten Problem
aufwirft: Gibt es einen stark polynomialen Algorithmus für die lineare Programmierung?
Joswig und seine Kollegen konnten nachweisen, dass eine der wichtigsten Klassen von LPAlgorithmen, die sogenannten „Log-barrier interior point methods“, dies nicht erfüllen.
Manche Experten hatten genau diese Verfahren bislang als heißeste Kandidaten für eine
positive Lösung betrachtet.

Würde man Smales neuntes Problem auf das genannte Supermarkt-Beispiel anwenden, so
stellt sich die praktische Frage: Wie stark wirkt sich die zusätzliche Berücksichtigung der
Koeffizienten, wie beispielsweise die konkreten Preise der Lebensmittel bzw. deren
Nährstoffgehalt, auf die Laufzeit aus? Die Wissenschaftler wiesen nach, dass die „Log-barrier interior point methods“ unerwarteter Weise viel länger brauchen, wenn die
Preise/Nährstoffgehalte sehr groß werden.

Negative Aussagen in der Komplexitätstheorie sind oft technisch anspruchsvoll, weil sie
erfordern, eine Vielzahl von Algorithmen zu prüfen. Die Beweismethode der Autoren basiert
vor allem auf Methoden aus der tropischen Geometrie, einem aktuellen mathematischen
Forschungsgebiet zwischen Optimierung, algebraischer Geometrie und Kombinatorik. In
Berlin untersucht Michael Joswig im Rahmen des Exzellenzclusters MATH+, ob die in der
ausgezeichneten Arbeit entwickelten tropischen Methoden auch zur Optimierung von
Auktionsverfahren beitragen können (Projekt AA3-5 Tropical Mechanism Design mit Max
Klimm). Die Berliner Mathematik verfügt über in Jahrzehnten aufgebaute Expertise zu
geometrischen Methoden in der linearen Optimierung (Martin Grötschel, Günter M. Ziegler).
Am MPI für Mathematik in den Naturwissenschaften in Leipzig fokussiert sich Joswig derzeit
auf die Entwicklung von Software für die mathematische Forschung, auch in der tropischen
Geometrie.

Die Society for Industrial and Applied Mathematics (SIAM) gibt 18 referierte Fachzeitschriften
heraus, die jedes Jahr insgesamt etwa 1500 wissenschaftliche Arbeiten in allen
Anwendungsbereichen der Mathematik veröffentlichen.

Information zu Professor Michael Joswig
https://page.math.tu-berlin.de/~joswig/

Informationen zur Society of Industrial and Applied Mathematics SIAM:
https://www.siam.org/

Wissenschaftlicher Ansprechpartner:
Professor Dr. Michael Joswig
E-Mail: joswig@math.tu-berlin.de
- Einstein Professor für Diskrete Mathematik/Geometrie
- Technische Universität Berlin / Institut für Mathematik
- MATH+: Forschungszentrum der Berliner Mathematik
- Max-Planck-Institut für Mathematik in den Naturwissenschaften

Originalpublikation:
Originalpublikation:
Publikation in SIAM Review 63 / 1:
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert und Michael Joswig
"What tropical geometry tells about the complexity of linear programming"
https://doi.org/10.1137/20M1380211
Einführung in den Artikel durch die Herausgeber:
https://epubs.siam.org/doi/abs/10.1137/21N975187

Weitere Informationen:
https://www.mis.mpg.de/de.html - Max-Planck-Institut für Mathematik in den Naturwissenschaften (MiS) in Leipzig
https://mathplus.de/ - Exzellenzcluster MATH+: Forschungszentrum der Berliner Mathematik