Two-Stage Robust Optimization for Mixed Integer and Linear Programs
This thesis investigates two-stage robust optimization as a fundamental framework for modeling and solving decision problems under uncertainty. In many real-world settings, a first-stage decision must be made before the realization of uncertain parameters, followed by a second-stage recourse that adapts to the observed outcome. The central aim of this work is to develop models and methods that preserve robustness of the solutions while remaining computationally tractable, particularly when approximations are necessary.
We first introduce a delay-resistant formulation of the vehicle routing problem, where travel and service times are uncertain. The first-stage consists of designing delivery routes, while the second-stage evaluates customer arrival times after the uncertainty realizes. A key contribution is a branch-and-price algorithm based on a path-based set partitioning model, equipped with customized column generation and problem-specific branching rules. This method computes provably robust routing plans and significantly reduces delays for real-world instances.
In the second part, we address the broader class of two-stage robust linear programs with right-hand side uncertainty, where the absence of exploitable structure makes exact optimization intractable. To tackle this, we introduce the General Polyhedral Approximation (GPA) framework, which approximates the uncertainty set by a union of polytopes derived from the vertex set of a dominating polytope. GPA significantly improves upon the simplex-based approximations in the literature by offering constant-factor improvements on the approximation factor while maintaining computational efficiency. It also provides a tunable trade-off between run time and solution quality. Building on this, we propose a new modeling paradigm: robust optimization under controllable uncertainty. In contrast to traditional robust optimization, where the uncertainty set is fixed, we allow the decision-maker to influence the structure of the uncertainty set through first-stage actions – such as modifying its geometry, or exploring uncertain components. This framework connects to models with decision-dependent information discovery. We will also develop tractable solution methods for specific classes of problems and discuss the effect of budget-deflection.
In the final chapter, we apply robust optimization concepts to the design of noise-minimizing aircraft trajectories. We develop a model that jointly computes time-dependent flight paths and determines the structure of airspace corridors in a discretized 3D space. Unlike existing approaches that separate these decisions, we solve them simultaneously using a column generation method.
Diese Dissertation untersucht die zwei-stufige robuste Optimierung als grundlegendes Gerüst zur Modellierung und Lösung von Entscheidungsproblemen unter Unsicherheit. In vielen realen Anwendungsszenarien muss eine erste Entscheidung vor der Realisierung unsicherer Parameter getroffen werden, gefolgt von einer zweiten, anpassbaren Entscheidung, die auf die beobachteten Ergebnisse reagiert. Ziel dieser Arbeit ist es, Modelle und Methoden zu entwickeln, die die Robustheit der Lösungen gewährleisten und gleichzeitig rechnerisch effizient bleiben – insbesondere in Fällen, in denen Approximationen erforderlich werden.
Den Anfang bildet eine robuste, verzögerungsresistente Variante des Vehicle Routing Problems, bei dem Fahr- und Servicezeiten im Voraus nicht exakt bekannt sind. Die erste Stufe besteht in der Planung der vorgesehenen Lieferrouten, während in der zweiten Stufe die tatsächlichen Ankunftszeiten bei den Kunden nach Realisierung der Unsicherheit bestimmt werden. Ein wesentlicher Beitrag dieser Arbeit ist ein Branch-and-Price-Verfahren, das auf einem pfadbasierten Set-Partitioning-Modell beruht und speziell angepasste Spaltengenerierung sowie problemspezifische Branchingregeln verwendet. Diese Methode berechnet nachweislich robuste Routenpläne und reduziert Verzögerungen in realitätsnahen Instanzen signifikant.
Im zweiten Teil der Arbeit widmen wir uns der allgemeinen Klasse zweistufiger robuster linearer Probleme mit Unsicherheit in der rechten Seite. Im Gegensatz zum vorherigen Kapitel fehlt hier eine ausnutzbare Struktur, wodurch eine optimale Lösung im Allgemeinen nicht berechenbar ist. Zur Lösung dieses Problems entwickeln wir das Konzept der General Polyhedral Approximation (GPA), bei dem die Unsicherheitsmenge durch eine Vereinigung von Polyedern approximiert wird, die aus den Ecken eines dominierenden Polyeders abgeleitet sind. GPA verbessert bestehende simplexbasierte Approximationsverfahren aus der Literatur deutlich, indem konstante Verbesserungen der Approximationsgüte bei gleichzeitig hoher Recheneffizienz erreicht werden. Darüber hinaus erlaubt das Verfahren einen steuerbaren Kompromiss zwischen Laufzeit und Lösungsqualität.
Darauf aufbauend schlagen wir ein neues Modellierungskonzept vor: Robuste Optimierung unter kontrollierbarer Unsicherheit. Im Gegensatz zur klassischen robusten Optimierung, bei der die Szenarienmenge als fix angenommen wird, erlauben wir es dem Entscheidungsträger, durch Maßnahmen in der ersten Stufe die Struktur der Unsicherheitsmenge aktiv zu beeinflussen – etwa durch geometrische Modifikationen oder gezielte Informationsgewinnung. Dieses Konzept steht in engem Zusammenhang mit Modellen unter dem Namen Decision-Dependent Information Discovery. Wir entwickeln praktisch lösbare Modellierungen für spezifische Problemklassen und analysieren den Einfluss von einem Effekt namens Budget Deflection.
Im abschließenden Kapitel übertragen wir die entwickelten Konzepte auf die Berechnung lärmarmer Flugtrajektorien. Wir entwerfen ein Modell, das gleichzeitig zeitabhängige Flugbahnen berechnet und die Struktur von Luftkorridoren in einem diskretisierten dreidimensionalen Luftraum bestimmt. Im Gegensatz zu bisherigen Ansätzen, die diese Entscheidungen entkoppelt betrachten, lösen wir beide Teilprobleme integriert mittels Spaltengenerierung.
Preview
Rights
Use and reproduction:
Access Statistic
