A primal-dual lifting scheme for two-stage robust optimization

File Description SizeFormat 
6261.pdfFile embargoed until 01 January 100001 MBAdobe PDF    Request a copy
Title: A primal-dual lifting scheme for two-stage robust optimization
Authors: Georghiou, A
Tsoukalas, A
Wiesemann, W
Item Type: Journal Article
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.
Date of Acceptance: 22-Mar-2019
URI: http://hdl.handle.net/10044/1/69686
ISSN: 0030-364X
Publisher: INFORMS
Journal / Book Title: Operations Research
Copyright Statement: This paper is embargoed until publication.
Sponsor/Funder: Engineering & Physical Science Research Council (E
Funder's Grant Number: EP/M028240/1
Keywords: Operations Research
0102 Applied Mathematics
0802 Computation Theory and Mathematics
1503 Business and Management
Publication Status: Accepted
Embargo Date: publication subject to indefinite embargo
Appears in Collections:Imperial College Business School

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commons