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

RAIRO - Operations Research - Recherche Opérationnelle (2014)

- Volume: 48, Issue: 4, page 455-475
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topMinoux, Michel. "Two-stage robust optimization, state-space representable uncertainty and applications." RAIRO - Operations Research - Recherche Opérationnelle 48.4 (2014): 455-475. <http://eudml.org/doc/275081>.

@article{Minoux2014,

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.},

author = {Minoux, Michel},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {robust optimization; graph algorithms; Min-Max optimization; min-max optimization},

language = {eng},

number = {4},

pages = {455-475},

publisher = {EDP-Sciences},

title = {Two-stage robust optimization, state-space representable uncertainty and applications},

url = {http://eudml.org/doc/275081},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 4

SP - 455

EP - 475

AB - 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.

LA - eng

KW - robust optimization; graph algorithms; Min-Max optimization; min-max optimization

UR - http://eudml.org/doc/275081

ER -

## References

top- [1] A. Ben Tal, A. Nemirovski, Robust solutions of linear programming problems contaminated with uncertain data. Math. Program.88 (2000) 695–715. Zbl0964.90025MR1782149
- [2] D.P. Bertsimas, M. Sim, Robust discrete optimization and network flows. Math. Program. B98 (2003) 49–71. Zbl1082.90067MR2019367
- [3] D.P. Bertsimas, M. Sim, The price of robustness. Oper. Res. 52(1) (2004) 35–53. Zbl1165.90565MR2066239
- [4] P. Carpentier, G. Cohen, J.C. Culioli, A. Renaud, Stochastic optimization of unit commitment: a new decomposition framework. IEEE Trans. Power Systems11 (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. Algorithms6 (1994) 245–273. Zbl0789.65045MR1323808
- [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. Combinatorica1 (1981) 169–197. Zbl0492.90056MR625550
- [8] C. Lemaréchal, A. Nemirovskii, Y. Nesterov, New variants of bundle methods. Math. Program.69 (1995) 111–147. Zbl0857.90102MR1354434
- [9] M. Minoux, Models and Algorithms for Robust PERT Scheduling with Time-Dependent Task Durations. Vietnam J. Math.35 (2007) 387–398. Zbl1142.90406MR2441686
- [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. Zbl1169.90325MR2507336
- [12] M. Minoux, Robust network optimization under polyhedral demand uncertainty is NP-hard. Discrete Appl. Math.158 (2010) 597–603. Zbl1185.90213MR2592467
- [13] M. Minoux, Solving some multistage robust decision problems with huge implicitly-defined scenario trees. Algorithmic Oper. Res.4 (2011) 1–18. Zbl1277.90082MR2481160
- [14] M. Minoux, On 2-stage robust LP with RHS uncertainty: complexity results and applications. J. Global Optim.49 (2011) 521–537. Zbl1213.90172MR2771618
- [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. Zbl1259.90084MR2980556
- [17] F. Ordoñez, J. Zhao, Robust capacity expansion of network flows. Networks50 (2007) 136–145. Zbl1144.90325MR2348336
- [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. Zbl0266.90046
- [21] A.L. Soyster, Inexact linear programming with generalized resource sets. EJOR3 (1979) 316–321. Zbl0405.90044MR534960

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.