K-adaptability in stochastic optimization

Abstract

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.