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.