Two-stage robust optimization, state-space representable uncertainty and applications

UPMC – LIP6 Boîte courrier 169. Couloir 26-00, Étage 4, Bureau 407, 4 place Jussieu, 75252 Paris Cedex 05, France.
minouxm@decision.lip6.fr

Received: 29 January 2014
Accepted: 11 March 2014

Abstract

The present paper addresses the class of two-stage robust optimization problems which can be formulated as mathematical programs with uncertainty on the right-hand side coefficients (RHS uncertainty). The wide variety of applications and the fact that many problems in the class have been shown to be NP-hard, motivates the search for efficiently solvable special cases. Accordingly, the first objective of the paper is to provide an overview of the most important applications and of various polynomial or pseudo-polynomial special cases identified so far. The second objective is to introduce a new subclass of polynomially solvable robust optimization problems with RHS uncertainty based on the concept of state-space representable uncertainty sets. A typical application to a multi period energy production problem under uncertain customer load requirements is described into details, and computational results including a comparison between optimal two-stage solutions and exact optimal multistage strategies are discussed.