Autor(en): Prünte, Jonas
Titel: K-adaptability in stochastic optimization
Sprache (ISO): en
Zusammenfassung: In dieser Dissertation untersuchen wir eine neue Strategie, um mit stochastischen Optimierungsproblemen umzugehen. Die stochastische Optimierung beschäftigt sich mit Problemen mit unsicheren Parametern. Unter der Annahme, dass die Verteilung dieser unsicheren Parameter bekannt ist, soll der Erwartungswert der Zielfunktion optimiert werden. Wir führen den Min-E-Min-Ansatz ein, bei dem anstatt einer Lösung K Lösungen berechnet werden. Nachdem die Realisierung der unsicheren Parameter beobachtet worden ist, wird die für die Realisierung beste Lösung ausgewählt. Wir untersuchen die Komplexität des Min-E-Min-Problems, indem wir NP-Schwere, parametrisierte Komplexität und Approximationseigenschaften detailliert analysieren. Wir zeigen, dass das Problem NP-schwer und W[2]-schwer ist, im Fall, dass K Teil des Inputs ist, selbst wenn die Menge der zulässigen Lösungen polynomiell von der Eingabegröße abhängt. Für festes K bleibt das Problem NP-schwer, wenn K größer als zwei ist. Zusätzlich beweisen wir, dass die Existenz eines polynomiellen Algorithmus mit einer konstanten Approximationsgüte für das Min-E-Min-Problem impliziert, dass P und NP gleich sind. Für das Min-E-Min-Problem mit kontinuierlicher Verteilung zeigen wir, dass allein das Evaluieren der Zielfunktion #P-schwer ist. Nichtsdestotrotz beweisen wir, dass man solche Probleme lösen kann, indem man die kontinuierliche Verteilung mit einer ausreichend großen Anzahl an Stichproben, welche derselben Verteilung folgen, diskretisiert. Neben den Komplexitätsresultaten stellen wir auch verschiedene exakte Algorithmen, unter anderem einen Branch-and-price-Algorithmus, zur Lösung des Problems vor. In einer ausführlichen experimentellen Untersuchung können wir belegen, dass je nach Situation jeder der vorgestellten Algorithmen am sinnvollsten sein kann. Darüber hinaus stellen wir verschiedene Varianten einer von uns entwickelten Heuristik vor und demonstrieren, dass diese das Min-E-Min-Problem schnell und genau lösen können. Zu guter Letzt betrachten wir auch verwandte Probleme und untersuchen ihre Komplexität.
Schlagwörter: Stochastic optimization
K-adaptability
Complexity theory
Schlagwörter (RSWK): Stochastische Optimierung
Komplexität
Algorithmus
URI: http://hdl.handle.net/2003/39766
http://dx.doi.org/10.17877/DE290R-21658
Erscheinungsdatum: 2020
Enthalten in den Sammlungen:Lehrstuhl V Diskrete Optimierung

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_Prünte.pdfDNB863.81 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource ist urheberrechtlich geschützt.



Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.