Entscheidungen zu treffen, ist nicht immer leicht, besonders wenn man dabei mehrere Ziele verfolgt. Computerprogramme können dabei helfen, indem sie Lösungen für komplexe Probleme in Feldern wie Produktion, Logistik und Mobilität finden. Doch selbst für hochentwickelte computergestützte Technologien ist es bis jetzt schwierig, die besten – die optimalen – Lösungen zu finden. Denn dabei müssen hunderte oder sogar tausende von Variablen berücksichtigt werden.
MOMIP
Sophie Parragh, Vorständin des Instituts für Produktions- und Logistikmanagement der Johannes Kepler Universität Linz, forschte in ihrem vom Wissenschaftsfonds FWF geförderten Projekt „MOMIP: Multi-Objective (Mixed) Integer Programming“ zusammen mit ihrem Team an neuen Algorithmen, die eine bestimmte Art solcher Optimierungsaufgaben lösen sollen: gemischt-ganzzahlige Probleme mit mehreren verschiedenen Zielen, die alle bestmöglich erfüllt werden sollen. „Man kann viele Probleme in der Wirtschaft als gemischt-ganzzahlige Systeme modellieren“, sagt die Forscherin. „Das sind mathematische Modelle, die Kosten, Ressourcen, Entscheidungen und vieles mehr umfassen.“
Die Anwendungsbeispiele für diese Algorithmen sind vielfältig: Beispielsweise kann man damit den CO2-Ausstoß in einer Produktionskette minimieren oder die optimalen Routen für geteilte elektrische Mobilität finden, die neben den Wartezeiten für die Kunden auch die Lärmbelastung für Anrainer so gering wie möglich halten sollen.
Variablen
Dass die Modelle gemischt-ganzzahlig sind, bedeutet, dass manche Variablen im Modell kontinuierlich sind – also alle möglichen Zahlen annehmen können – und manche Variablen nur bestimmte ganze Zahlen annehmen können wie null oder eins. Zum Beispiel ist die Länge des Anfahrtswegs eines Lieferservice eine kontinuierliche Variable, denn der Transporter kann beliebig lange Umwege fahren, um gewisse Straßen zu vermeiden, und somit die Wegstrecke länger machen. Im Gegensatz dazu ist der Entschluss zum Aufbau eines Paketverteilerzentrums eine ganzzahlige Variable, denn dieses kann nur ganz (dargestellt als „1“) oder gar nicht (dargestellt als „0“) errichtet werden.
Neben den gemischt-ganzzahligen Variablen ist der zweite Kernpunkt der Aufgabenstellung, der sich Parragh und ihr Team widmen, mehrere Ziele gleichzeitig zu erfüllen. Das stellt die Forschenden vor besondere Herausforderungen, ermöglicht aber auch nuanciertere Lösungsansätze.
Viele Ziele – viele Lösungen
„Bisher etablierte Algorithmen können vor allem Aufgaben mit nur einem Ziel lösen. Daher können sie auch nur eine optimale Lösung finden, doch das ist nicht immer hilfreich“, sagt Parragh. So ist es etwa bei der Zustellung von Paketen ein naheliegendes Ziel, die Transportkosten so gering wie möglich zu halten. Doch der alleinige Fokus auf die Kosten lässt andere Ziele unter den Tisch fallen.
„Algorithmen mit mehreren Zielen wie der unsere können eine Gruppe an optimalen Lösungen finden, die verschiedene Kompromisse abbilden“, erklärt Parragh. „Eine der Lösungen erzeugt vielleicht die geringsten Kosten, aber verursacht mehr CO2-Emissionen. Eine andere Lösung kostet vielleicht etwas mehr, erzeugt aber weniger Emissionen. Und es gibt noch viele andere Lösungen dazwischen.“
Mehr Handlungsspielraum für Führungskräfte
Im Rahmen ihres Projekts suchten die Forschenden also nach einem Verfahren, das die optimalen Lösungen für verschiedene Arten komplexer Probleme findet. Annäherungen an die besten Lösungen konnten schon von etablierten Programmen gefunden werden, doch das Ziel von Parragh und ihrem Team ist es, allgemeine Algorithmen zu schaffen, die mathematisch bewiesen die optimalen Lösungen für viele verschiedene Problemstellungen finden.
Nicht nur auf ein Ziel konzentrieren
Mit den nuancierten Lösungen, die ihre Programme produzieren, möchten Parragh und ihr Team Entscheidungsträgern in Wirtschaft und Politik mehr Handlungsspielraum geben. „Wir haben in unseren Modellen gesehen, dass Ziele wie reduzierte Emissionen, Umweltschutz oder auch höhere Kundenzufriedenheit darunter leiden, wenn man sich nur auf die Kostenoptimierung fokussiert“, fügt Parragh hinzu. „Diese Ziele können oft viel besser erfüllt werden, wenn man nur etwas mehr Kosten in Kauf nimmt.“
Verzweigte Algorithmen
„Bei den Problemen, an denen wir arbeiten, schlägt die Kombinatorik zu. Das heißt, dass die Anzahl der möglichen Kombinationen an Variablen für verschiedene Lösungen enorm schnell ansteigt, sodass wir damit nicht mehr einfach umgehen können“, erklärt die Computerwissenschaftlerin. Zusammen mit ihrem Team – Nicolas Forget, Fabien Tricoire, Duleabom An, Markus Sinnl und Miriam Enzi – und internationalen Kooperationspartnern entwickelte sie sogenannte Branch-and-Bound-Algorithmen.
Bei den Branch-and-Bound-Verfahren wird die Menge aller möglichen Lösungen – also nicht nur die optimalen – in kleinere Gruppen geteilt, um sie einzeln zu betrachten. Das Programm kann dann schneller entscheiden, ob die gesuchten optimalen Lösungen überhaupt in einer dieser Gruppen liegen, anstatt alle Lösungen auf einmal zu untersuchen.
Falls die Berechnungen ergeben, dass die optimalen Lösungen nicht in der untersuchten Gruppe liegen können, werden die Lösungen darin verworfen. Falls die optimalen Lösungen enthalten sein können, kann man den Algorithmus der Gruppe in noch kleinere Gruppen zerteilen und immer weitersuchen lassen. Mit diesen Verzweigungen findet das Programm schließlich die optimalen Lösungen, welche die vorausgesetzten Ziele mit verschiedenen Kompromissen erfüllen.
Wichtiger Meilenstein
Parragh fasst zusammen: „Einer der Meilensteine am Ende des Projekts war, dass wir einen Algorithmus für Systeme mit etwa 100 ganzzahligen Entscheidungsvariablen und für drei oder sogar vier Ziele entwickelt haben, der mit anderen etablierten Methoden konkurrieren kann. Wir arbeiten nun daran, diese Programme weiterzuentwickeln.“
Entwicklung geht weiter
Auch nach Abschluss des Projekts „MOMIP: Multi-Objective (Mixed) Integer Programming“ im September 2022 führten Parragh und ihr Team die Arbeit fort. Sie verfeinerten ihre Algorithmen, um beispielsweise das Risikobewusstsein von Entscheidungsträgern zu modellieren, neue Anwendungsfelder zu erschließen oder die Berechnungen effektiver zu machen. Der Bedarf an nuancierten Lösungen für die Probleme unserer komplexen Gesellschaft wird auch in Zukunft sicherlich nicht abreißen.
Über Sophie Parragh
Die Wirtschafts- und Computerwissenschaftlerin studierte internationale Betriebswirtschaft an der Universität Wien. Als Postdoc forschte Parragh am IBM Center for Advanced Studies in Porto und hatte anschließend eine vom FWF finanzierte Hertha-Firnberg-Stelle inne. Nach einer Gastprofessur an der Wirtschaftsuniversität Wien habilitierte sie sich 2016 an der Universität Wien. Seit März 2017 leitet Sophie Parragh das Institut für Produktions- und Logistikmanagement an der Johannes Kepler Universität Linz. In ihrer Forschungsarbeit befasst sie sich mit der Entwicklung von Optimierungsverfahren zur Entscheidungsunterstützung in Produktion und Logistik. Das Projekt „MOMIP: Multi-Objective (Mixed) Integer Programming“ (2018–2022) wurde vom Wissenschaftsfonds FWF mit rund 390.000 Euro gefördert.
