A Primal–Dual Lifting Scheme for Two-Stage Robust Optimization
| Autor: | Wolfram Wiesemann, Angelos Tsoukalas, Angelos Georghiou |
|---|---|
| Přispěvatelé: | Department of Technology and Operations Management, Engineering & Physical Science Research Council (E |
| Rok vydání: | 2020 |
| Předmět: |
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 |
| Zdroj: | Operations Research, 68, 572-590. INFORMS Institute for Operations Research and the Management Sciences |
| ISSN: | 0030-364X |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|