K-Adaptability in Two-Stage Robust Binary Programming

• 成果类型: Article
• 署名作者: Hanasusanto, Grani A.; Kuhn, Daniel; Wiesemann, Wolfram
• 署名单位: Imperial College London; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2015.1392
• 发表日期: 2015
• 页码: 877-891
• 关键词: approximation algorithms; stochastic programs; integer recourse; decomposition algorithm; finite adaptability; optimization; FRAMEWORK; POWER; cut

摘要

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.