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

Angelos Georghiou (), Angelos Tsoukalas () and Wolfram Wiesemann
Additional contact information
Angelos Georghiou: Desautels Faculty of Management, McGill University, Montreal, Quebec H3A 0G4, Canada
Angelos Tsoukalas: Olayan School of Business, American University of Beirut, 1107-2020 Lebanon
Wolfram Wiesemann: Imperial College Business School, Imperial College London, London SW7 2AZ, United Kingdom

Operations Research, 2020, vol. 68, issue 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: robust optimization; two-stage problems; decision rules; error bounds (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1873 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:2:p:572-590

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().