Two-stage robust optimization, state-space representable uncertainty and applications
RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 4, pp. 455-475.

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.

DOI : 10.1051/ro/2014017
Classification : 90C47, 90C27
Mots-clés : 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},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {4},
     year = {2014},
     doi = {10.1051/ro/2014017},
     mrnumber = {3270128},
     language = {en},
     url = {http://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2014017/

[1] A. Ben Tal, A. Nemirovski, Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88 (2000) 695-715. | MR | Zbl

[2] D.P. Bertsimas, M. Sim, Robust discrete optimization and network flows. Math. Program. B 98 (2003) 49-71. | MR | Zbl

[3] D.P. Bertsimas, M. Sim, The price of robustness. Oper. Res. 52(1) (2004) 35-53. | MR | Zbl

[4] P. Carpentier, G. Cohen, J.C. Culioli, A. Renaud, Stochastic optimization of unit commitment: a new decomposition framework. IEEE Trans. Power Systems 11 (2012) 1067-1073.

[5] J.C. Dodu, T. Eve, M. Minoux, Implementation of a proximal algorithm for linearly constrained nonsmooth optimization problems and computational results. Numer. Algorithms 6 (1994) 245-273. | MR | Zbl

[6] A. Frangioni, C. Gentile, F. Lacalandra, Solving unit commitment problems with general ramp constraints. Int. J. Electr. Power Energ. Syst. 30 (2008) 316-326.

[7] M. Grötschel, L. Lovász, A. Schrijver, The Ellipsoid Method and its consequences in combinatorial optimization. Combinatorica 1 (1981) 169-197. | MR | Zbl

[8] C. Lemaréchal, A. Nemirovskii, Y. Nesterov, New variants of bundle methods. Math. Program. 69 (1995) 111-147. | MR | Zbl

[9] M. Minoux, Models and Algorithms for Robust PERT Scheduling with Time-Dependent Task Durations. Vietnam J. Math. 35 (2007) 387-398. | MR | Zbl

[10] M. Minoux, Robust Linear Programming with Right-Hand-Side Uncertainty, Duality and Applications, in Encyclopedia of Optimization, edited by L.A. Floudas and P.M. Pardalos, 2nd edn. (2008) 3317-3327.

[11] M. Minoux, On robust maximum flow with polyhedral uncertainty sets. Optim. Lett. 3 (2009) 367-376. | MR | Zbl

[12] M. Minoux, Robust network optimization under polyhedral demand uncertainty is NP-hard. Discrete Appl. Math. 158 (2010) 597-603. | MR | Zbl

[13] M. Minoux, Solving some multistage robust decision problems with huge implicitly-defined scenario trees. Algorithmic Oper. Res. 4 (2011) 1-18. | MR | Zbl

[14] M. Minoux, On 2-stage robust LP with RHS uncertainty: complexity results and applications. J. Global Optim. 49 (2011) 521-537. | MR | Zbl

[15] M. Minoux, Efficient robust multistage optimization with state-space representation of uncertainty and applications (Submitted).

[16] M. Minoux, Two-stage robust LP with ellipsoidal RHS uncertainty is NP-hard. Optim. Lett. 6 (2012) 1463-1475. | MR | Zbl

[17] F. Ordoñez, J. Zhao, Robust capacity expansion of network flows. Networks 50 (2007) 136-145. | MR | Zbl

[18] J. Ostrowski, M.F. Anjos, A. Vannelli, Tight mixed integer linear programming formulations for the unit commitment problem. IEEE Trans. Power Syst. 27 (2012) 39-46.

[19] N.P. Padhy, Unit commitment - A bibliographical survey. IEEE Trans. Power Syst. 19 (2004) 1196-1205.

[20] A.L. Soyster, Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21 (1973) 1154-1157. | Zbl

[21] A.L. Soyster, Inexact linear programming with generalized resource sets. EJOR 3 (1979) 316-321. | MR | Zbl

Cité par Sources :