Die Wirtschafts- und Computerwissenschaftlerin Sophie Parragh erforscht, wie man bessere und vor allem nuanciertere Lösungen für komplexe Probleme finden kann. Dazu programmiert sie Algorithmen, welche die manchmal widersprüchlichen Ziele in vielen Bereichen der Wirtschaft, wie Logistik oder Produktion, darstellen können.

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.

Vielfältige Anwendungsbereiche

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 Kund:innen auch die Lärmbelastung für Anrainer:innen so gering wie möglich halten sollen. Ein weiteres Beispiel ist die effiziente Planung von mobilen Pflegediensten. Dabei ist es nicht nur wichtig, dass genug Zeit für die Betreuung vorhanden ist, sondern auch, dass die gewünschten Pflegekräfte und Besuchszeiten der Kund:innen Beachtung finden.

Variablen von flexibel bis fix definieren

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."

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.

Mit den nuancierten Lösungen, die ihre Programme produzieren, möchten Parragh und ihr Team Entscheidungsträger:innen 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 Kooperationspartner:innen 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.

Projekt-Meilenstein

Parragh fasst zusammen: "Einer der Meilensteine am Ende des Projekts war, dass wir einen Algorithmus für Systeme mit etwa hundert 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."

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äger:innen zu modellieren, neue Anwendungsfelder zu erschließen oder die Berechnungen effektiver zu machen. Die Forschungsteams können sich sicher sein, dass der Bedarf an nuancierten Lösungen für die Probleme unserer komplexen Gesellschaft auch in Zukunft nicht abreißen wird.

Zur Person

Sophie Parragh studierte internationale Betriebswirtschaft an der Universität Wien. Als Postdoc forschte sie 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.

Publikationen

Forget N., Parragh S. N.: Enhancing Branch-and-Bound for Multiobjective 0-1 Programming, in: INFORMS Journal on Computing 2024

An D., Parragh S. N., Sinnl M., Tricoire F.: A matheuristic for tri-objective binary integer linear programming, in: Computers & Operations Research 2024

Parragh S.N., Tricoire F., Gutjahr W.J.: A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem, in: OR Spectrum 2022