NIMROp: Neue Unsicherheitsmodelle für die Robuste Optimierung
Theoretische Informatik
Zusammenfassung der Projektergebnisse
Die robuste Optimierung hat sich zu einer führenden Methode zur Behandlung von Entscheidungsproblemen unter Unsicherheit entwickelt. Sie ermöglicht es den Entscheidungsträgern, die Unsicherheit proaktiv einzubeziehen, so dass eine Lösung gefunden werden kann, die auch dann noch gut funktioniert, wenn die Problemparameter von ihren erwarteten Werten abweichen. Ein Teil des Erfolgs der robusten Optimierung besteht darin, dass sie relativ einfach anzuwenden ist. Wir brauchen die Wahrscheinlichkeitsverteilung über die Problemparameter nicht zu kennen, was in der Praxis oft der Fall ist. Wir müssen lediglich eine Menge von Szenarien festlegen, gegen die wir unsere Entscheidung absichern wollen, die so genannte Unsicherheitsmenge. Die Komplexität des robusten Problems hängt davon ab, welche Art von Unsicherheitsmenge verwendet wird. Eine Liste von Szenarien ist zum Beispiel oft einfach zu bestimmen, hat aber den Nachteil, dass das resultierende Problem schwer zu lösen ist. Mit der Einführung von budgetierten Unsicherheitsmengen steht ein Modellierungswerkzeug zur Verfügung, das sowohl einfach zu interpretieren und intuitiv zu definieren ist als auch zu leicht lösbaren robusten Problemen führt. Das Wissen über solche Arten von Unsicherheitsmengen ist daher ein zentraler Faktor für den Erfolg der robusten Optimierung. In diesem Projekt betrachten wir eine Alternative zu solchen Mengen, die sich auf Kardinalitäten bezieht, die entweder im Ziel oder in den Nebenbedingungen des Problems vorkommen. Die Unsicherheit bedeutet, dass einige der Elemente, die wir in der Lösung nutzen wollen, später nicht mehr verfügbar sind (z. B. ist ein Arbeiter in einem Team, das mit der Ausführung einer bestimmten Aufgabe betraut ist, eine Zeit lang nicht mehr verfügbar). Die Unsicherheitsmenge wird durch eine Budgetbeschränkung definiert. Wir können ein Worst-Case-Szenario für diese Situation auf sehr ähnliche Weise finden wie bei klassischen budgetierten Unsicherheitsmengen. Die Fragen, die wir untersuchen, sind daher, wie komplex die resultierenden robusten Optimierungsprobleme sind und wie sie am besten gelöst werden können. Wir konnten die Frage der Komplexität negativ beantworten, indem wir gezeigt haben, dass das Problem nicht nur im Allgemeinen schwer zu lösen ist, sondern nicht einmal ein Approximationsverfahren zulässt. Um das Problem zu lösen, haben wir verschiedene Umformulierungen des Problems eingeführt, die dann leicht in Verbindung mit handelsüblicher Lösungssoftware verwendet werden können. Diese Modelle lassen sich auch auf Kardinalitätsbeschränkungen ausdehnen, die in komplexeren Kontexten auftreten, z. B. bei Problemen, bei denen es exponentiell viele solcher Beschränkungen gibt. Wir konnten zeigen, dass unsere Lösungsmethoden trotz der theoretischen Schwierigkeit des Problems Probleme von angemessener Größe behandeln können.
Projektbezogene Publikationen (Auswahl)
-
Robust combinatorial optimization problems under budgeted interdiction uncertainty. OR Spectrum, 47(1), 255-285.
Goerigk, Marc & Khosravi, Mohammad
