Back to Search Start Over

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

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

Authors :
Wolfram Wiesemann
Angelos Tsoukalas
Angelos Georghiou
Department of Technology and Operations Management
Engineering & Physical Science Research Council (E
Source :
Operations Research, 68, 572-590. INFORMS Institute for Operations Research and the Management Sciences
Publication Year :
2020

Abstract

Two-stage robust optimization problems, in which decisions are taken both in anticipation ofand in response to the observation of an unknown parameter vector from within an uncertaintyset, are notoriously challenging. In this paper, we develop convergent hierarchies of primal (con-servative) and dual (progressive) bounds for these problems that trade off the competing goalsof tractability and optimality: While the coarsest bounds recover a tractable but suboptimalaffine decision rule approximation of the two-stage robust optimization problem, the refinedbounds lift extreme points of the uncertainty set until an exact but intractable extreme pointreformulation of the problem is obtained. Based on these bounds, we propose a primal-duallifting scheme for the solution of two-stage robust optimization problems that accommodatesfor discrete here-and-now decisions, infeasible problem instances as well as the absence of a rela-tively complete recourse. The incumbent solutions in each step of our algorithm afford rigorouserror bounds, and they can be interpreted as piecewise affine decision rules. We illustrate theperformance of our algorithm on illustrative examples and on an inventory management problem.

Details

ISSN :
0030364X
Volume :
68
Database :
OpenAIRE
Journal :
Operations Research
Accession number :
edsair.doi.dedup.....b5ba1000dc7f9778b9f3528ff372e001
Full Text :
https://doi.org/10.1287/opre.2019.1873