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

Michel Minoux

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

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

Abstract

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

How to cite

top

Minoux, 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. [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. [2] D.P. Bertsimas, M. Sim, Robust discrete optimization and network flows. Math. Program. B98 (2003) 49–71. Zbl1082.90067MR2019367
  3. [3] D.P. Bertsimas, M. Sim, The price of robustness. Oper. Res. 52(1) (2004) 35–53. Zbl1165.90565MR2066239
  4. [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. [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. [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. [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. [8] C. Lemaréchal, A. Nemirovskii, Y. Nesterov, New variants of bundle methods. Math. Program.69 (1995) 111–147. Zbl0857.90102MR1354434
  9. [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. [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. [11] M. Minoux, On robust maximum flow with polyhedral uncertainty sets. Optim. Lett.3 (2009) 367–376. Zbl1169.90325MR2507336
  12. [12] M. Minoux, Robust network optimization under polyhedral demand uncertainty is NP-hard. Discrete Appl. Math.158 (2010) 597–603. Zbl1185.90213MR2592467
  13. [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. [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. [15] M. Minoux, Efficient robust multistage optimization with state-space representation of uncertainty and applications (Submitted). 
  16. [16] M. Minoux, Two-stage robust LP with ellipsoidal RHS uncertainty is NP-hard. Optim. Lett.6 (2012) 1463–1475. Zbl1259.90084MR2980556
  17. [17] F. Ordoñez, J. Zhao, Robust capacity expansion of network flows. Networks50 (2007) 136–145. Zbl1144.90325MR2348336
  18. [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. [19] N.P. Padhy, Unit commitment – A bibliographical survey. IEEE Trans. Power Syst.19 (2004) 1196–1205. 
  20. [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. [21] A.L. Soyster, Inexact linear programming with generalized resource sets. EJOR3 (1979) 316–321. Zbl0405.90044MR534960

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.