A Primal-Dual Lifting Scheme for Two-Stage Robust Optimization

• 成果类型: Article
• 署名作者: Georghiou, Angelos; Tsoukalas, Angelos; Wiesemann, Wolfram
• 署名单位: McGill University; American University of Beirut; Imperial College London
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1873
• 发表日期: 2020
• 页码: 572-590
• 关键词: Robust Optimization; two-stage problems; Decision rules; error bounds

摘要

Two-stage robust optimization problems, in which decisions are taken both in anticipation of and in response to the observation of an unknown parameter vector from within an uncertainty set, are notoriously challenging. In this paper, we develop convergent hierarchies of primal (conservative) and dual (progressive) bounds for these problems that trade off the competing goals of tractability and optimality: Although the coarsest bounds recover a tractable but suboptimal affine decision rule approximation of the two-stage robust optimization problem, the refined bounds lift extreme points of the uncertainty set until an exact but intractable extreme point reformulation of the problem is obtained. Based on these bounds, we propose a primal-dual lifting scheme for the solution of two-stage robust optimization problems that accommodates for discrete, here-and-now decisions, infeasible problem instances, and the absence of a relatively complete recourse. The incumbent solutions in each step of our algorithm afford rigorous error bounds, and they can be interpreted as piecewise affine decision rules. We illustrate the performance of our algorithm on illustrative examples and on an inventory management problem.