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.
Keywords: robust optimization, graph algorithms, Min-Max optimization
@article{RO_2014__48_4_455_0,
author = {Minoux, Michel},
title = {Two-stage robust optimization, state-space representable uncertainty and applications},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {455--475},
year = {2014},
publisher = {EDP-Sciences},
volume = {48},
number = {4},
doi = {10.1051/ro/2014017},
mrnumber = {3270128},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2014017/}
}
TY - JOUR AU - Minoux, Michel TI - Two-stage robust optimization, state-space representable uncertainty and applications JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2014 SP - 455 EP - 475 VL - 48 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2014017/ DO - 10.1051/ro/2014017 LA - en ID - RO_2014__48_4_455_0 ER -
%0 Journal Article %A Minoux, Michel %T Two-stage robust optimization, state-space representable uncertainty and applications %J RAIRO - Operations Research - Recherche Opérationnelle %D 2014 %P 455-475 %V 48 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2014017/ %R 10.1051/ro/2014017 %G en %F RO_2014__48_4_455_0
Minoux, Michel. Two-stage robust optimization, state-space representable uncertainty and applications. RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 4, pp. 455-475. doi: 10.1051/ro/2014017
Cité par Sources :