Ressourcen schonen mit Mathematik
| 13. April 2016
Mit Mathematik die Umwelt schonen: Wie kann zum Beispiel Obst beim Transport oder im Supermarkt so platz- und damit ressourcensparend wie möglich gestapelt werden? An solchen und anderen globalen Optimierungsproblemen arbeiten Mathematiker der Universität Wien in einem aktuellen FWF-Projekt. (Foto: Universität Wien)
Ob beim Stapeln von Obst, Beladen eines LKWs oder Ausstanzen von Blechteilen: In einem aktuellen FWF-Projekt suchen Mathematiker der Universität Wien unter der Leitung von Hermann Schichl nach Algorithmen, die dabei helfen, Ressourcen zu sparen.
Hermann Schichl will die Welt verbessern – mit Mathematik. "Globale Optimierung" nennt sich das mathematische Gebiet, auf dem er forscht und wo es darum geht, die bestmögliche Lösung für komplexe Probleme zu finden. Eben für Probleme, wie sie nicht nur in der reinen Mathematik existieren, sondern auch in der echten Welt – also der "Realwelt", mathematisch gesprochen.
"Wenn wir wirklich nachhaltig wirtschaften und die Umwelt schonen möchten, müssen wir Wege finden, um mit weniger Ressourcen auszukommen. Zum Beispiel Methoden, um die Herstellungsprozesse von Gütern so zu optimieren, dass nur die Minimalmenge an Ressourcen verbraucht wird und keine Verschwendung passiert", erklärt Hermann Schichl vom Institut für Mathematik die Anwendungsmöglichkeiten seines 2015 gestarteten und vom Wissenschaftsfonds FWF geförderten Forschungsprojekts.
Der Mathematiker Hermann Schichl leitet das dreijährige FWF-Projekt "Dekompositionsverfahren für globale Optimierung". (Foto: Universität Wien)
Viele Dinge, wenig Platz
Typische globale Optimierungsprobleme sind in der angewandten Mathematik z.B. sogenannte Packungsprobleme. Dabei geht es, banal formuliert, um die Frage, wie Dinge am besten platziert werden müssen, um auf kleinstem Raum möglichst viele davon unterzubringen.
Die Herausforderung steigt bei zunehmender Anzahl. "Packungsprobleme sind für viele Industriebereiche relevant, beispielsweise wenn es darum geht, bei der Ausstanzung aus Blechen den Verschnitt so gering wie möglich zu halten. Oder Paletten in einem LKW so zu stapeln, dass möglichst viele hineinpassen", erklärt Projektleiter Hermann Schichl.
Globale Optimierungsprobleme sind komplex
Packungsprobleme sind in ihrer Eigenschaft "NP-hard" (dt.: NP-schwer). "Die Frage, ob ein Problem in P liegt oder ob es NP-schwer ist, beeinflusst den Lösungsprozess. Bislang existiert kein effizienter Algorithmus, der eine optimale Lösung für NP-schwere-Probleme geben kann. Denn die Zeit, die zur Berechnung benötigt wird, steigt exponenziell zur Größe des Problems an, d.h. gerechnet wird nicht n hoch 2, sondern 2 hoch n", erläutert der Mathematiker. Das bedeutet, dass die Rechenzeit sehr schnell ansteigt: Denn während beispielsweise 50 hoch 2 noch überschaubar ist, ergibt 2 hoch 50 eine so hohe Zahl, dass es illusorisch ist, auf das Ende der Berechnung zu warten.
Ein Entscheidungsproblem ist in NP, wenn Beweise für eine Ja-Antwort effizient (d.h. in polynomialer Zeit) verifiziert werden können. Das Finden eines solchen Beweises (d.h. das Lösen des Problems) ist in der Regel viel schwieriger. Ein Problem ist NP-schwer ("NP-hard"), wenn es mindestens so schwierig zu lösen ist wie alle NP-Probleme.
"Ist ein Problem also z.B. 50-mal so groß wie das Ausgangsproblem, kann der ursprüngliche Algorithmus die Lösung nicht mehr berechnen. Selbst wenn man alle Computer dieser Welt zusammenschalten würde, bräuchte die Berechnung immer noch länger, als unser Universum überhaupt existiert", so der sympathische Mathematiker über die Komplexität der globalen Optimierungsprobleme.
Den Kuchen aufteilen
Weil Optimierungsprobleme, die in realistischen Anwendungen auftreten, oft riesig sind, versuchen die Mathematiker der Universität Wien, sie in kleine Teilprobleme zu zerlegen und für jedes Stück den passenden Lösungsalgorithmus anzuwenden. Auf diese Weise – mit einem sogenannten Dekompositionsverfahren – verringert sich der Rechenaufwand.
Stellen wir uns vor: Im Supermarkt sollen zehn Zitronen und zehn Orangen auf kleinstmöglichem Raum gestapelt werden. Um die optimale Lösung zu finden, ist es sinnvoll, nicht mit 20 Früchten, sondern mit 2 x 10 Obststapeln zu rechnen. "20 Dinge zu stapeln ist 1000-mal so schwierig wie zehn Dinge zu stapeln. Hingegen ist das Stapeln von 2 x 10 Dingen nur zweimal so schwierig. Wenn wir die Zitronen und Orangen also getrennt berechnen, haben wir einen Faktor 500 an der Lösungszeit gespart. Das ist die Grundlage von Dekompositionsverfahren", so Hermann Schichl, der auch in der Lehre bemüht ist, seinen Studierenden durch praktische Beispiele Mathematik greifbar zu machen. 2013 wurde er für seine innovativen Lehr- und Lernkonzepte mit dem "UNIVIE Teaching Award" ausgezeichnet.
Die sieben "Millennium Problems"
Das Clay Mathematics Institute (CMI) in Massachusetts veröffentlichte im Jahr 2000 eine Liste mit sieben ungelösten Problemen der Mathematik. Mit in der Liste ist auch das P-NP-Problem, in dem es um die Beziehung der beiden Komplexitätsklassen P und NP zueinander geht. Für die Lösung eines dieser sieben Probleme vergibt das Institut jeweils eine Million US-Dollar Preis-Geld. Bislang konnte nur eines der sieben Probleme gelöst werden.
Doch ganz so einfach ist es nicht, denn die Teilprobleme stehen nicht unabhängig nebeneinander, sondern haben viele kleine Verbindungen, in der Mathematik Nebenbedingungen genannt. Allein das Finden der bestmöglichen Stückelung eines Problems ist ein Optimierungsproblem für sich. Denn, ebenso wie beispielsweise beim Aufteilen eines Kuchens, stehen viele Möglichkeiten zur Auswahl. "Unser Ziel ist es, möglichst kleine Teile mit kleinen Verbindungen zu finden."
Neue Algorithmen für bessere Lösungen
Für diese Aufgabe schreiben Hermann Schichl und sein Team Computerprogramme. Wenn deren Algorithmen ein Teilproblem gelöst haben, wird überprüft, ob es die optimale Lösung ist. Wenn nicht, wird eine weitere relevante Nebenbedingung ergänzt. "Computeralgorithmen finden heutzutage Lösungen, die im Durchschnitt 15 bis 20 Prozent besser sind als das, was ein Mensch herausfinden könnte. Denn die Anzahl der möglichen Kombinationen ist einfach zu hoch. Große Probleme haben an die 10.000 Variablen und 10.000 bis 20.000 Gleichungen und Ungleichungen."
Das Schreiben der Computerprogramme ist ein fortlaufender und langwieriger Prozess (Bild: Hermann Schichl). Im aktuellen Forschungsprojekt arbeitet die Gruppe von Hermann Schichl beispielsweise mit einem Programm namens COCONUT, das vor zwölf Jahren entstand und immer weiter wächst.
Auf der Suche nach der optimalen Lösung
Methodisch arbeiten die Wissenschafter mit dem sogenannten Branch-and-Bound-Verfahren, d.h. sie versuchen, Algorithmen zu generieren, die mit Sicherheit die besten Lösungen finden und für alle globalen Optimierungsprobleme anwendbar sind. "Im Moment liegt die realistische Grenze bei 20 bis 50 Variablen. Unser Ziel ist, Algorithmen zu erforschen, die Probleme mit 200 bis 1.000 Variablen zuverlässig lösen können. Wenn wir das bis zum Ende des Projekts schaffen, bin ich sehr zufrieden", konstatiert Schichl.
Die von ihnen entwickelten Computerprogramme stellen die Mathematiker als Open Source kostenlos zur Verfügung. Denn für Hermann Schichl ist Nachhaltigkeit mehr als nur eine leere Worthülse: "Jede und jeder kann sich unsere Programme herunterladen. Das ist unser Beitrag zum nachhaltigen Umgang mit Ressourcen. Um die Programme effektiv nutzen zu können, braucht es dann aber wohl doch wieder einen Mathematiker oder eine Mathematikerin." (mw)
Das dreijährige FWF-Projekt "Dekompositionsverfahren für globale Optimierung" läuft bis 31. August 2018 unter der Leitung von ao. Univ.-Prof. Dipl.-Ing. Dr. Hermann Schichl vom Institut für Mathematik der Universität Wien.
