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}, publisher = {EDP-Sciences}, volume = {48}, number = {4}, year = {2014}, doi = {10.1051/ro/2014017}, mrnumber = {3270128}, language = {en}, url = {http://archive.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://archive.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://archive.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, Volume 48 (2014) no. 4, pp. 455-475. doi : 10.1051/ro/2014017. http://archive.numdam.org/articles/10.1051/ro/2014017/

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

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

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

, ,[4] Stochastic optimization of unit commitment: a new decomposition framework. IEEE Trans. Power Systems 11 (2012) 1067-1073.

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

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

, , ,[7] The Ellipsoid Method and its consequences in combinatorial optimization. Combinatorica 1 (1981) 169-197. | MR | Zbl

, , ,[8] New variants of bundle methods. Math. Program. 69 (1995) 111-147. | MR | Zbl

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

,[10] 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] On robust maximum flow with polyhedral uncertainty sets. Optim. Lett. 3 (2009) 367-376. | MR | Zbl

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

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

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

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

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

,[17] Robust capacity expansion of network flows. Networks 50 (2007) 136-145. | MR | Zbl

, ,[18] Tight mixed integer linear programming formulations for the unit commitment problem. IEEE Trans. Power Syst. 27 (2012) 39-46.

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

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

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

,*Cited by Sources: *