K-adaptability in two-stage robust binary programming

Grani A. Hanasusanto, Daniel Kuhn, Wolfram Wiesemann

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)877-891
Number of pages15
JournalOperations Research
Issue number4
StatePublished - Jul 1 2015
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'K-adaptability in two-stage robust binary programming'. Together they form a unique fingerprint.

Cite this