Optimization Online


K-Adaptability in Two-Stage Robust Binary Programming

Grani Adiwena Hanasusanto (g.hanasusanto11***at***imperial.ac.uk)
Daniel Kuhn (daniel.kuhn***at***epfl.ch)
Wolfram Wiesemann (ww***at***imperial.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"

Download: [PDF]

Entry Submitted: 03/28/2014
Entry Accepted: 03/28/2014
Entry Last Modified: 03/30/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society