Optimization Online


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

Angelos Georghiou(angelos.georghiou***at***mcgill.ca)
Angelos Tsoukalas(at60***at***aub.edu.lb)
Wolfram Wiesemann(ww***at***imperial.ac.uk)

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: While 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 generic polyhedral uncertainty sets, infeasible problem instances as well as 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

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 10/10/2017
Entry Accepted: 10/10/2017
Entry Last Modified: 10/10/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society