NIMROp: Neue Unsicherheitsmodelle für die Robuste Optimierung

• Antragsteller: Professor Dr. Marc Goerigk
• Fachliche Zuordnung: Accounting und Finance ; Theoretische Informatik
• Förderung: Förderung von 2021 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 459533632

Optimierungsmodelle und -algorithmen sind zu mächtigen Werkzeugen für die Entscheidungsfindung und darüber hinaus geworden. Klassische Methoden sind für den optimistischen Fall entwickelt worden, dass alle Informationen über das Entscheidungsproblem verfügbar sind. In der Praxis ist das nur selten der Fall: Die Zukunft ist unbekannt und Prognosen werden verwendet, Messdaten sind ungenau, und Störungen können einen Plan unbrauchbar machen.Robuste Optimierung (RO) bietet einen Ansatz, um Entscheidungen zu treffen, bei denen solche Unsicherheiten im Vorfeld berücksichtigt werden. Im Mittelpunkt der RO steht dabei das Modell der Unsicherheit. In den meisten RO-Ansätzen muss eine Lösung alle Szenarien berücksichtigen, die in einer Unsicherheitsmenge enthalten sind, ohne Verwendung von Wahrscheinlichkeiten. Dies kann auch als ein Spiel mit zwei Spielern gesehen werden, bei dem ein Gegner versucht, eine Lösung mit den durch die Unsicherheitsmenge gegebenen Möglichkeiten zu stören. Das bedeutet, dass Lösungen zu konservativ werden, wenn die Unsicherheitsmenge zu groß ist. Die Wahl der Unsicherheit wird zusätzlich dadurch erschwert, dass sie die Komplexität des resultierenden RO-Problems beeinflusst. Eine komplexe Unsicherheitsmenge kann zu Optimierungsproblemen führen, die nicht in angemessener Zeit gelöst werden können.Aus diesen Gründen ist eine Kernliste von Unsicherheitsmengen, die einen guten Kompromiss zwischen Modellierungsleistung und Komplexität bieten, eine treibende Kraft für die Forschung in RO. Der vielleicht populärste Ansatz ist die budgetierte Unsicherheit, bei der eine einzelne Nebenbedingung die Größe der möglichen Abweichung für unsichere Koeffizienten steuert.Bei der Betrachtung eines Problems der Personaleinsatzplanung wurde uns klar, dass keines der derzeit verfügbaren Unsicherheitsmodelle geeignet ist, Situationen zu behandeln, bei der das Ziel des Gegners darin besteht, so viele Jobs wie möglich unter einer Budgetbeschränkung zu stören. Wir bezeichnen dies als ein RO-Problem mit bounded interdiction.Das Ziel dieses 18-monatigen Projekts ist es, eine detaillierte Studie über RO mit bounded interdiction durchzuführen. Wir analysieren die Komplexität solcher Probleme, leiten Approximationsergebnisse ab, entwickeln kompakte Modellformulierungen und exakte Lösungsalgorithmen, erweitern bounded interdiction auf allgemeinere Situationen wie z.B. zweistufige Probleme und evaluieren den Ansatz auf realen Datensätzen.Die Auswirkungen, die die Einführung von budgetierten Unsicherheiten auf Forschung und Anwendung im Bereich der RO hatte, zeigt das Potential guter Unsicherheitsmodelle. Mit dem vorgeschlagenen Ansatz erweitern wir die Möglichkeiten der RO, um eine breitere Klasse von Entscheidungsfindungsproblemen zu behandeln, und eröffnen gleichzeitig einen interessanten Weg für weitere methodologische Forschung.

• DFG-Verfahren: Sachbeihilfen