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
- 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.
- Subjects :
- Mathematical optimization
Technology
Operations Research
Lifting scheme
two-stage problems
Computer science
POWER
Social Sciences
robust optimization
UNIT COMMITMENT
Management Science and Operations Research
COMPUTATION
Set (abstract data type)
PROGRAMS
DESIGN
Business & Economics
0102 Applied Mathematics
0802 Computation Theory and Mathematics
Science & Technology
DECISION RULES
FINITE ADAPTABILITY
Operations Research & Management Science
Robust optimization
SUMS
Decision rule
error bounds
Computer Science Applications
Primal dual
Management
Anticipation (artificial intelligence)
1503 Business and Management
Stage (hydrology)
APPROXIMATION
Subjects
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