Sequential Decision Making under System-inherent Uncertainty: Mathematical Optimization Methods for Time-dynamic Applications
Final Report Abstract
Ausgehend von uneinheitlichen und oftmals sehr problem-spezifischen Vorgehensweisen bei der Anwendung von mathematischen Verfahren für mehrstufige zeitdynamische Optimierungsprobleme bestand das Hauptanliegen dieses Projekts in der Erarbeitung eines umfassenden Modellierungs-Frameworks für diese Problemklasse. Hiermit sollte eine vereinheitlichende Behandlung der Faktoren „Zeit“ und „Unsicherheit“ erreicht werden, um Problemstellungen in Methoden-übergreifender Form behandeln und verschiedenen Optimierungsparadigmen (Online-Optimierung mit Lookahead, mehrstufige stochastische Programmierung und robuste Optimierung) zugänglich machen zu können. Einhergehend mit der Modellierung des Daten- und Lösungsprozesses stellte sich zudem die Frage, wie Bewertungen der Algorithmenqualität vorzunehmen sind, um einen Vergleich der Ergebnisse auch über Optimierungsparadigmen hinweg zu ermöglichen. Schließlich bestand ein wesentliches Ziel dieses Forschungsvorhabens in der Validierung des Frameworks in praktischen Problemstellungen. Neben der Einordnung existierender Verfahren zur mehrstufigen mathematischen Optimierung unter Unsicherheit resultiert aus der ersten Projektphase ein Modellierungs-Framework für zeitdynamische mehrstufige Optimierungsprobleme unter Unsicherheit. Dessen wesentliches Merkmal ist eine strikte Trennung der Modellierung des mehrstufigen Entscheidungsprozesses (repräsentiert durch einen Online-Verfahrensablauf), der Modellierung des (unsicheren und dynamischen) Datenprozesses und der Beschreibung des (dynamischen und auf Schnappschussproblemen beruhenden) Lösungsprozesses. Das Framework ist allgemeiner als existierende Ansätze, da es weder einer Begrenzung des Planungshorizonts bedarf noch eine additive Zusammensetzung des Gesamtzielfunktionswerts aus Zielfunktionswerten einzelner Zeitstufen voraussetzt. Somit kann es ähnlich einer rollierenden Planung eingesetzt werden und ermöglicht die Einbindung verschiedener mathematischer Optimierungsverfahren unter Unsicherheit in dieses Planungsvorgehen. In der zweiten Projektphase erfolgte dann eine generische Implementierung des Frameworks in C++. Im Zusammenspiel mit der Instanziierung für das Lot Sizing Problem lieferte die Software-Umgebung die Grundlage für die Untersuchungen hinsichtlich der Einsatzfähigkeit des Frameworks und der daraus ableitbaren Aussagen über den Einsatz von Methoden der Online-Optmierung mit Lookahead, der mehrstufigen stochastischen Programmierung und robusten Optimierung in einer praktischen Anwendung. Da für die Analyse der Problemstellung ein rechenintensiver Sampling-Einsatz nötig wurde, lässt sich folgern, dass ein derart hoher Aufwand bei der Nutzung des Frameworks nur dann empfohlen werden kann, wenn eine hohe Detailtiefe in der Analyse der eingesetzten Lösungsverfahren benötigt wird. Dies wäre beispielsweise der Fall, wenn man sich im Detail für die Differenz in den zu erwartenden Zielfunktionswerten unterschiedlicher Optimierungsparadigmen interessiert. Ein vor Projektbeginn nicht zu erwartendes Ergebnis betrifft den Einsatz des Online-Verfahrensablaufs im Kontext einer adaptiven Steuerung der logistischen Prozesse beim Transport von Testproben aus Testzentren zu Laboren. Diese Forschungsarbeit entstand als Beitrag zur Bewältigung der Corona-Krise. Da im Anwendungsfall deutlich wurde, dass andere Wege beschritten werden müssen, um Rechenzeiten zu reduzieren, wurde zudem für die dynamische mehrstufige Truck Relocation ein Benders-Dekompositionsverfahren umgesetzt, um doch noch mit exakten mathematischen Verfahren an die Lösung von Schnappschussproblemen herangehen zu können. Angesichts des hohen Rechenaufwands wäre für einen weiteren Einsatz zu überlegen, heuristische Verfahren oder die Nutzung von Metamodellen als weniger rechenintensive Alternativen zur exakten Lösung von Schnappschussproblemen durch mathematische Programmierung in Erwägung zu ziehen.
Publications
- A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice, Omega (United Kingdom), 2020, 96, 102080
Bakker, H., Dunke, F., Nickel, S.
(See online at https://doi.org/10.1016/j.omega.2019.06.006) - Modeling Multi-stage Decision Making under Incomplete and Uncertain Information, technical report, 2020
Bindewald, V., Dunke, F., Nickel, S.
- Tackling Uncertainty in Lot Sizing – Comparison of Different Disciplines, extended conference abstract, 2021
Bindewald, V., Dunke, F., Nickel, S.
- GIT-Bereitstellung der Implementierung des Modellierungs- und Lösungs- Frameworks in C++ und zugehörige Instanziierung für das Lot Sizing Problem
Bindewald, V.
- Comparison of different approaches to multi-stage lot sizing with uncertain demand. International Transactions in Operational Research, Vol. 30. 2023, Issue 6, pp. 3771–3800.
Bindewald, V., Dunke, F., Nickel, S.
(See online at https://doi.org/10.1111/itor.13305) - Exact reoptimization in online optimization with gradual look-ahead, International Journal of Systems Science: Operations and Logistics, Vol. 10. 2023, Issue 1, 2141590.
Dunke, F., Nickel, S.
(See online at https://doi.org/10.1080/23302674.2022.2141590) - Logistics for Diagnostic Testing: an Adaptive Decision-support Framework, European Journal of Operational Research, 2023 (Available online 25 May 2023)
Bakker, H., Bindewald, V., Dunke, F., Nickel, S.
(See online at https://doi.org/10.1016/j.ejor.2023.05.028)
