A Primal-Dual Lifting Scheme for Two-Stage Robust Optimization
- 1 March 2020
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 68 (2) , 572-590
Abstract
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.Keywords
This publication has 52 references indexed in Scilit:
- Solving two-stage robust optimization problems using a column-and-constraint generation methodOperations Research Letters, 2013
- Robust counterparts of inequalities containing sums of maxima of linear functionsEuropean Journal of Operational Research, 2013
- Robust resource allocations in temporal networksMathematical Programming, 2011
- On the power and limitations of affine policies in two-stage adaptive optimizationMathematical Programming, 2011
- Theory and Applications of Robust OptimizationSIAM Review, 2011
- Primal and dual linear decision rules in stochastic and robust optimizationMathematical Programming, 2009
- Convex Hull Computations2004
- Adjustable robust solutions of uncertain linear programsMathematical Programming, 2004
- Degeneracy graphs: theory and application an updated surveyAnnals of Operations Research, 1993
- Stochastical approximation of convex bodiesMathematische Annalen, 1985