K-Adaptability in Two-Stage Robust Binary Programming
Grani A. Hanasusanto, Daniel Kuhn, Wolfram Wiesemann
Operations Research · 2015 · Volume 63 · Issue 4
Abstract
Over the last two decades, robust optimization has emerged as a computationally attractive approach to formulate and solve single-stage decision problems affected by uncertainty. More recently, robust optimization has been successfully applied to multistage problems with continuous recourse. This paper takes a step toward extending the robust optimization methodology to problems with integer recourse, which have largely resisted solution so far. To this end, we approximate two-stage robust binary programs by their corresponding K -adaptability problems, in which the decision maker precommits to K second-stage policies, here -and-now, and implements the best of these policies once the uncertain parameters are observed. We study the approximation quality and the computational complexity of the K -adaptability problem, and we propose two mixed-integer linear programming reformulations that can be solved with off-the-shelf software. We demonstrate the effectiveness of our reformulations for stylized instances of supply chain design, route planning, and capital budgeting problems.
Keywords
programming, integer, stochastic
Enable JavaScript for citation tools and additional paper interactions.