K-Adaptability in Two-Stage Robust Binary Programming
Grani Adiwena Hanasusanto (g.hanasusanto11imperial.ac.uk)
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 multi-stage problems with continuous recourse. This paper takes a step towards 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 pre-commits 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: Robust optimization, integer programming, two-stage problems.
Category 1: Robust Optimization
Category 2: Integer Programming
Citation: The paper was previously titled "Two-Stage Robust Integer Programming"
Entry Submitted: 03/28/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|