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

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.