TY  - THES
A3  - Lorenz, Ulf
AB  - Das in der Mitte des letzten Jahrhunderts etablierte Forschungsgebiet der Optimierung unter Unsicherheit hat in den letzten beiden Jahrzehnten viel Aufmerksamkeit erhalten. Der Umgang mit unsicheren Daten in Optimierungsproblemen bleibt aber trotz (oder gerade wegen) der Zeiten großer Datenmengen und Cloud-Lösungen eine große Herausforderung. Die bekanntesten Ansätze um mit solchen Optimierungsproblemen umzugehen sind stochastische Programmierung und robuste Optimierung. Um ein realistischeres Abbild des zugrunde liegenden Problems zu ermöglichen, können dabei auch mehrstufige Modelle zum Einsatz kommen. Während es einige echt-mehrstufige stochastische Ansätze gibt, gehen die meisten mehrstufigen Erweiterungen der robusten Optimierung nicht über ein zweistufiges Modell hinaus. Noch weniger Aufmerksamkeit wird der Berücksichtigung von entscheidungsabhängiger Unsicherheit geschenkt. Um diese Lücke zu schließen, wurden in dieser Arbeit mehrstufige Optimierungsprobleme auch mit entscheidungsabhängiger Unsicherheit mittels quantifizierter Programme untersucht.
Mit quantifizierten Programmen können mehrstufige Optimierungsprobleme unter Unsicherheit formuliert werden. Dabei handelt es sich um  lineare Programme, deren Variablen mit jeweils einem Existenz- oder einem Allquantor versehen sind und eine feste Reihenfolge aufweisen. Die erzielten Fortschritte für quantifizierte lineare Programme gaben Anlass zur näheren Untersuchung von quantifizierten ganzzahligen Programmen (QIP) in dieser Arbeit. Während sich ein Großteil der Forschung in diesem Bereich der komplexitätstheoretischen Untersuchung  spezieller QIP-Erfüllbarkeitsprobleme widmet, war das vorrangige Ziel dieser Arbeit neue Lösungstechniken und Unsicherheitskonzepte für das QIP-Optimierungsproblem zu erforschen.
QIPs können durch eine Spielbaumsuche gelöst werden, welche durch Techniken aus den Bereichen des SAT-, QBF- und MIP-Lösens erweitert werden können. Weitere Lösungstechniken, die in eine solche Spielbaumsuche mit einfließen,  wurden in der vorliegenden Arbeit entwickelt und fundiert. Insbesondere wurde die Strategic Copy-Pruning Heuristik etabliert. Diese erlaubt es die Existenz einer Strategie in linearer Zeit implizit sicherzustellen, ohne diese explizit durchlaufen zu müssen. Außerdem konnte gezeigt werden, dass die Umsetzung der erlangten Ergebnisse den Suchprozess erheblich beschleunigen kann.
Um die Ausdrucksfähigkeit von QIPs zu erhöhen, wurden darüber hinaus QIPs mit polyedrischer Unsicherheitsmenge eingeführt. Infolge dieser Erweiterung konnten verschiedene mehrstufige kombinatorische Optimierungsprobleme deutlich schneller gelöst werden. Durch eine zusätzliche Erweiterung wurde außerdem ein allgemeiner Rahmen für mehrstufige Optimierungsprobleme unter entscheidungsabhängiger Unsicherheit geschaffen. In dieser Arbeit wurden dafür Lösungstechniken theoretisch fundiert, Implementierungsdetails bereitgestellt und explizite Polynomzeitreduktionen hergeleitet.
AU  - Hartisch, Michael
DA  - 2020
DO  - 10.25819/ubsi/4841
KW  - Robuste Optimierung
KW  - Robust Optimization
KW  - Multistage Optimization
KW  - Combinatorial Search
KW  - Game Tree Search
KW  - Optimization under Uncertainty
KW  - Mehrstufige Optimierung
KW  - Spielbaumsuche
KW  - Optimierung unter Unsicherheit
LA  - eng
PY  - 2020
TI  - Quantified integer programming with polyhedral and decision-dependent uncertainty
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:467-17058
Y2  - 2024-11-22T09:03:02
ER  -