In monopolistic environment for energy transmission network capacities were designed with a wide safety margin, so for a long time expansion planning in electrical energy systems was concentrated on generation expansion planning (GEP) with the goal to cover cumulative demand uncertainty based on averaged historic demand data. These were modeled as stochastic optimization problems with a one dimensional demand distribution represented by 2-stage or multi-stage scenario trees that were generated by Monte Carlo methods. The models went to the limit of computational possibilities at any point in time,
included binary decision variable, with a risk neutral approach and, then, only expected values in the objective function where considered in the time horizon over the scenarios. Very limited use was made of risk averse measures.
In order to solve the large scale problems, decomposition methods played a central role, in particular the following methodologies:
- Two-stage Benders Decomposition (BD) for linear problems [11]. See [8,37,55], among many others.
- Multistage Benders Decomposition (BD) methodology for linear problems. See [13] among others.
- Two-stage Lagrangean Decomposition (LD) heuristic methodology. See [14,1718,29,28,33,41,42], among many others. See also [2, 56] for two surveys on the state-of-the-art of two-stage stochastic unit commitment, and using LD with bundle methods. See also [1,16,51] two-stage LD approaches with bundle methods applied to energy problems.
- Multistage Clustering Lagrangean Decomposition (MCLD) heuristic methodology. See [21,22,23,38], among some others.
- Regularization methods. See [9, 33, 39, 49, 50, 53], among others.
- Progressive Hedging algorithm (PHA) for multistage primal decomposition. See [47,57], among others.
- Multistage Stochastic Dynamic Programming (SDP). See [4,15,25,26,30,32,40,44,45,48,54], among others.
- Multistage cluster primal decomposition. See [5,7,10,19,24,38,43,52,58], among others.
- Parallelized decomposition algorithms. See [3,4,5,6,9,12,34,39,43,48,52,58], among others.
Today, new power production possibilities, technological developments and deregulation bring along several new sources of uncertainty with highly differing levels of variability. In addition to traditional demand these are foremost dependencies on wind, market prices, mobile electricity consumers like cars, power exchanges on international level, local energy producers on distribution network level and, to a lesser extent, solar radiation. This introduces complex and volatile load and demand structures that pose a severe challenge for strategic planning in production and transmission and, on a shorter time scale, in distribution. Networks may now be equipped with new infrastructure like Phase Measurement Units (PMUs) and other information technology in order to improve their cost efficiency. At the same time these upgraded networks should ensure high standards in reliability in their daily use and resilience against natural or human caused disasters. Companies now have teams devoted to the task of generating suitable planning data.
In optimization models, the emphasis has shifted to high dimensional stochastic data and to considering risk reduction measures instead of expected values. Computationally integrated models considering all relevant aspects are out of scope. Even for simplified models it is often difficult or not known how to provide stochastic data of sufficient quality [63]. Alternatives are then:
- robust optimization, where distributions are replaced by "easier" uncertainty sets [59],
- fuzzy methods, where uncertainties are replaced by a kind of interval arithmetic equipped with scenario dependent probabilities [60],
- information gap decision theory that aims at hedging against information errors [61,62].
Methods for solving these stochastic optimization problems with binary decision variables employ the same decomposition approaches listed above, but much more care needs to be devoted to the properties of the decomposition. For risk averse measures in multistage models, methods are distinguished regarding their "time consistency" or "time inconsistency". So far, stochastic dynamic programming approaches are the most suitable ones for dealing with the time consistency property of risk measures, so that the original stochastic problem may be decomposed more easily via scenario clustering and cluster dependent risk levels.
In power generation optimization models for big companies the following are the issues of relevance, mainly addressed in the context of market competition:
- when and where to install how much new production capacity, mainly considering wind generators and thermal plants (decisions on nuclear power are political)
- how to extend or renew hydro plants and where to install what pumping capacities. Today, solar power is typically handled at the level of distribution networks.
In contrast, competition is not an issue for transmission and distribution network operators. Regulations on efficiency, reliability and resilience levels are the driving force in the following problems:
- when and where to install how much network capacity and information equipment,
- reducing transmission losses,
- reducing distribution losses (technical and detecting non-technical ones).
Challenges today and for the future comprise:
- The robust approach allows for safe optimization with uncertain data. What information can be extracted from these robust solutions e.g. on which additional data would be needed to improve the quality of the model?
- Several risk averse measures have been proposed, each with its advantages and disadvantages. How to make use of them in the best way?
- How to deal with endogenous uncertainty, i.e., with optimizing big player decisions that influence the probability distributions that are optimized over?
- How to construct hierarchical decomposition approaches in a consistent way?
- How to make use of high performance computing (HPC, multi-core or Distributed) in decomposition approaches?
- How to integrate chance constraints (ICC), e.g. with respect to reliability or resilience?
General goals for future models include: increasing the level of integration; bringing models closer to reality by avoiding the excessive linearization of nonlinear aspects; reducing the gap between methods used in academia and those applied in practice; making use of new monitoring devices and communication systems; exploring the chances of cooperation between electric and other energy commodity systems.
References
[1] W van Ackooij and C. Sagastizabal. Constrained bundle methods for upper inexact oracles with application to join chance constrained energy problems. SIAM Journal on Optimization, 24:733-765, 2014.
[2] W. van ackooij and J. Malick. Decomposition algorithm for large-scale two-stage unitcommitment. Annals of Operatiosn Research, 238:587-613, 2016.
[3] U. Aldasoro, L.F. Escudero, M. Merino and G. Perez. An algorithmic framework for solving large-scale multistage stochastic mixed 0-1 problems with nonsymmetric scenario trees. Part II: Parallelization. Computers & Operations Research, 40:2950-2960, 2013.
[4] U. Aldasoro, L.F. Escudero, M. Merino, J.F. Monge and G. Perez. On parallelization of a Stochastic Dynamic Programming algorithm for solving large-scale mixed 0-1 problems under uncertainty. TOP, 23:703-742, 2015.
[5] U. Aldasoro, L.F. Escudero, M. Merino, J.F. Monge and, G. Perez. A parallel Branch-and-Fix Coordination based matheuristic algorithm for solving large-scale multistage stochastic mixed 0-1 problems. Submitted.
[6] T. Al-Khamisl and R. MHallah. A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity. Computers & Operations Research, 38:17471759, 2011.
[7] A. Alonso-Ayuso, L.F. Escudero and M.T. Ortuño. BFC, a Branch-and-Fix Coordination algorithmic framework for solving stochastic 0-1 programs. European Journal of Operational Research, 151:503-519, 2003.
[8] L. Aranburu, L.F. Escudero, M.A. Garin, G. Perez, A so-called Cluster Benders Decomposition approach for solving two-stage stochastic linear programs, TOP, 20:279-295, 2012.
[9] T. Asamov and W.B. Powell. Regularized Decomposition of HighDimensional Multistage Stochastic Programs with Markov Uncertainty. arXiv: 1505,02227, 2015.
[10] C. Beltran-Royo, L.F. Escudero, J.F. Monge and R.E. Rodriguez-Ravines. An effective heuristic for multistage stochastic linear optimization. Computers & Operations Research, 51:237-250, 2014.
[11] J.F. Benders. Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik, 14:238-252, 1962.
[12] P. Beraldi, L. Grandinetti, R. Musmanno and C. Triki. Parallel algorithms to solve two-stage stochastic linear programs with robustness constraints. Parallel Computing, 26:18891908, 2000.
[13] J.R. Birge. Decomposition and partitioning methods for multi-stage stochastic linear programs. Operations Research, 33:989-1007, 1985.
[14] C.C. Carøe and R. Schultz. Dual decomposition in stochastic integer programming. Operations Research Letters, 24:37-45, 1999.
[15] M.P. Cristobal, L.F. Escudero and J.F. Monge. On Stochastic Dynamic Programming for solving large-scale tactical production planning problems. Computers & Operations Research, 36:2418-2428, 2009.
[16] G. Emiel and C. Sagastizabal. Incremental like bundle methods with applications to energy planning. Computational Optimization and Applications, 46:305-332, 2009.
[17] L.F. Escudero, A. Garin, M. Merino, and G. Perez. A general algorithm for solving two-stage stochastic mixed 0-1 first-stage problems. Computers & Operations Research, 36:2590-2600, 2009.
[18] L.F. Escudero, A. Garin, G. Perez, and A. Unzueta. Scenario cluster decomposition of the Lagrangian dual in two-stage stochastic mixed 0-1 optimization. Computers & Operations Research, 40:362-377, 2013.
[19] L.F. Escudero, A. Garíi, M. Merino and G. Perez. An algorithmic framework for solving large-scale multistage stochastic mixed 0-1 problems with nonsymmetric scenario trees. Computers & Operations Research, 39:1133-1144, 2012.
[20] L.F Escudero, A. Garin, M. Merino, and G. Perez. A decomposition framework for solving dynamic MINLP problems under uncertainty. Workshop on Mixed Integer Nonlinear Programming, Workshop on Mixed Integer Nonlinear Programming, WMINLP2014. http://minlp.cheme.cmu.edu/2014/index.html. Carnegie Mellon University, Pittsburgh (PA, USA), 2014.
[21] L.F. Escudero, A. Garin and A. Unzueta. Cluster Lagrangean decomposition in multistage stochastic optimization. Computers & Operations Research, 67:48-62, 2016.
[22] L.F. Escudero, M.A. Garn, C. Pizarro and A. Unzueta. On the strongest Lagrangean bounds for stochastic location-assignment problems. Submitted.
[23] L.F. Escudero, M.A. Garin and A. Unzueta. Cluster Lagrangean decomposition for time stochastic dominance induced by mixed integer-linear recourse in multistage stochastic optimization. Submitted.
[24] L.F. Escudero, A. Garin, M. Merino, and G. Perez. On time stochastic dominance induced by mixed-integer linear recourse in multistage stochastic programs. European Journal of Operational Research, 249:164-176, 2016.
[25] L.F. Escudero, J.F. Monge and D. Romero-Morales. An SDP approach for multiperiod mixed 0–1 linear programming models with stochastic dominance constraints for risk management. Computers & Operations Research, 58:32-40, 2015.
[26] L.F. Escudero, J.F. Monge and D. Romero-Morales. On time-consistent stochastic dominance risk averse measure for Tactical Supply Chain Planning under uncertainty. Submitted.
[27] L.F. Escudero, J.F. Monge, D. Romero-Morales and J.Wang. Expected Future Value Decomposition Based Bid Price Generation for Large-Scale Network Revenue Management. Transportation Science, 47:181-197, 2013.
[28] R. Gollmer, F. Neise and R. Schultz. Stochastic programs with first-order stochastic dominance constraints induced by mixed-integer linear recourse. SIAM Journal on Optimization, 19:552-571, 2008.
[29] R. Gollmer, U. Gotzes and R. Schultz. A note on second-order stochastic dominance constraints induced by mixed-integer linear recourse. Mathematical Programming Ser.A, 126:179-190, 2011.
[30] V. Guigues. SDDP for some interstage dependent risk averse problems and application to hydrothermal planning Computational Optimization & Applications, 57:167-203, 2014.
[31] E. Klerides and E. Hadjiconstantinou. A decomposition-based stochastic programming approach for the project scheduling problem under time/cost trade-off setting and uncertain durations. Computers & Operations Research, 37:2131-2140, 2010.
[32] V. Kozmik and D. P. Morton. Risk-averse stochastic dual dynamic programming. Optimization Online, org/DB HTML/2013/02/3794, 2013.
[33] Z.Li and M. Ierapetritou. Capacity expansion planning through augmented Lagrangian optimization and scenario decomposition. AIChE Journal, 58:871-883, 2012.
[34] J. Linderoth, A. Shapiro, and S.Wright. The empirical behavior of sampling methods for stochastic programming. Annals of Operations Research, 142:215241, 2006.
[35] G. Lulli and S. Sen. A branch and price algorithm for multistage integer programs with application to stochastic batch sizing problems. Management Science, 50:787-796, 2004.
[36] G. Lulli and S. Sen. A heuristic procedure for stochastic integer programs with complete recourse. European Journal of Operational Research, 879-890, 2006.
[37] S. Lumbreras and A. Ramos. Optimal design of the electrical layout of an offshore wind farm applying decomposition strategies. IEEE Transactions on Power Systems, 28:1434-1441, 2013.
[38] D. Mahlke. A scenario tree-based decomposition for solving multistage stochastic programs with applications in energy production. Springer, 2011.
[39] J.M. Mulvey and A. Ruszczynski. A new scenario decomposition method for large scale stochastic optimization. Operations Research, 43:477-490, 1995.
[40] M.P. Nowak and W. Roemisch. Stochastic Lagrangean relaxation applied to power scheduling under uncertainty. Annals of Operations Research, 100:251-272, 2000.
43:477-490, 1995.
[41] F. Oliveira, V. Gupta, S. Hamacher, and I.E. Grossmann. A Lagrangean decomposition approach for oil supply chain investment planning under uncertainty with risk considerations. Computers and Chemical Engineering, 50:184-195, 2013.
[42] W. Oliveira, C. Sagastizabal, and S. Scheimberg. Inexact bundle methods for two-stage stochastic programming. SIAM Journal on Optimization, 21:517-544, 2011.
[43] A. Pages-Bernaus, G. Perez-Valdes and A. Tomasgard. A parallelised distributed implementation of a Branch and Fix Coordination algorithm. European Journal of Operational Research, 244:77-85, 2013.
[44] M.V.F. Pereira and L.M.V.G. Pinto. Stochastic optimization of a multireservoir hydroelectric system, a decomposition approach. Water Resources Research, 21:779–792, 1985.
[45] M.V.F. Pereira and L.M.V.G. Pinto. Multistage stochastic optimization applied to energy planning. Mathematical Programming, 52:359–375, 1991.
[46] A.R. de Queiroz and D.P. Morton. Sharing cuts under aggregated forecasts when decomposing multi-stage stochastic programs. Operations Research Letters, 31:311-316, 2013.
[47] R.T. Rockafellar and R.J-B. Wets. Scenario and policy aggregation in optimisation under uncertainty. Mathematics of Operations Research, 16:119147, 1991.
[48] A. Ruszczynski. Parallel decomposition of multistage stochastic programming problems Mathematical Programming, 58:201-228, 1993.
[49] A. Ruszczynski. On the convergence of an augmented lagrangian decomposition method for sparse convex optimization. Mathematics of Operations Research, 634-566, 1995.
[50] A. Ruszczynski and A. Swietanowski. Accelerating the regularized decomposition method for two stage stochastic linear problems. SIAM Journal on Optimization, 24:127-153, 2014.
[51] C. Sagastizabal. Divide to conquer: Decomposition methods for energy optimization. Mathematical Programming Ser. B, 134:187-222, 2012.
[52] B. Sandikci and O.Y. Ozaltin. A scalable bounding method for multi-stage stochastic integer programs. Technical report, Working paper 14-21, Booth School of Business, University of Chicago, Chicago, IL, USA, 2014. URL http://dx.doli.org/10.21.39/ssrn.26666.
[53] S. Sen and Z. Zhou. Multistage stochastic decomposition: a bridge between stochastic programming and approximate dynamic programming. SIAM Journal on Optimization, 24:1278-153, 2014.
[54] A. Shapiro, W. Tekaya, J.P. da Costa and M. Pereira. Risk neutral and risk averse stochastic dual dynamic programming method. European Journal of Operational Research, 224:375-391, 2013.
[55] R. van Slyke R. and R.B.Wets. L-shaped linear programs with application to optimal control and stochastic programming. SIAM Journal on Applied Mathematics, 17:638-663, 1969.
[56] M. Tahanan, W. van Ackooij, A. Frangioni and F. Lacalandra. Large-scale unit commitment under uncertainty. 4OR, 13:115-171, 2015.
[57] J.P.Watson and D.Woodruff. Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. Computational Management Science, 8:355370, 201
[58] G.L. Zenarosa, O.A. Prokopyev, and A.J. Schaefer. Scenario-tree decomposition: Bounds for multistage stochastic mixed-integer programs. Technical report, Technical paper, Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA, USA, 2014. URL http://dx.doli.org/10.21.39/ssrn.26666.
[59] Ben-Tal, Aharon, and Arkadi Nemirovski. "Robust optimization–methodology and applications." Mathematical Programming 92.3 (2002): 453-480.
[60] Zadeh, Lotfi Asker. "Fuzzy sets as a basis for a theory of possibility." Fuzzy sets and systems 1.1 (1978): 3-28.
[61] Ben-Haim, Yakov. Info-gap decision theory: decisions under severe uncertainty. Academic Press, 2006.
[62] A. Rabiee, A. Soroudi and A. Keane, "Information Gap Decision Theory Based OPF With HVDC Connected Wind Farms," in IEEE Transactions on Power Systems, vol. 30, no. 6, pp. 3396-3406, Nov. 2015.
[63] Soroudi, Alireza, and Turaj Amraee. "Decision making under uncertainty in energy systems: state of the art." Renewable and Sustainable Energy Reviews 28 (2013): 376-384
Contributors:
Prof. Laureano Escudero, Universidad Rey Juan Carlos
Dr Alireza Soroudi, University College Dublin (UCD)
Prof. Christoph Helmberg, TU Chemnitz