K-Adaptability in Two-Stage Robust Binary Programming

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.