Page tree

Versions Compared


  • This line was added.
  • This line was removed.
  • Formatting was changed.


In the past (say, up to 25 years ago) practically all over the world the energy sector was a very centralized one where the Generation Companies (GenCoselectricity generating companys) had a reduced decision-making on generation expansion capacity planning. The energy prices were centrally decided as well as the main geographical areas where to service the energy demand. So, the maximization of profit functions was out of question and, then, the main goal was to minimize the net present value (NPV) of the global cost for the planning of the site, location and capacity of new energy generation sources in, first, hydropower, second, variety of thermal plants, and also in the too-much controversial nuclear generation. In the latter energy source, not too-much room was left for the modeling tools to help in the decision making. On the other hand, the claims of other stakeholders (mainly, environmentalist ones) were not a strong issue given the strong regulation of the sector. The modeling could consider uncertainty on the main parameters that, by definition of the non-open market and, then, its strong regulation, was reduced to macro-economic and demographic factors that influence the energy demand to serve and the generation disruption. On the other side, the state-of-the-art on theory, modeling and algorithms for dealing with mathematical optimization under uncertainty (i.e., stochastic optimization) was not as advanced as it is today and, sure, will be in the future. Additionally, the HW/SW computer power was so low (until, say, 10-15 years ago) that the gigantic models that were needed to provide solutions to help the decision-making could not be considered.

Today the situation has drastically changed. The HWThe hardware/SW software computer power capability is very high, and it seems that its exponential growth will continue at least in the near future. On the other hand, some stochastic optimization tools could be considered today as a sort of commodities ready to be used. Additionally, the energy sector is very different from what it was in the past. It continues being a crucial sector for the European economy as for the rest of the world. However, its market, without being fully an open one (something that, by definition, probably it cannot be), it allows higher freedom to the GenCo for performing strategic energy generation capacity expansion planning in a long horizon. First, there is enough freedom on deciding the amount of power generation from the different plants / farms and, on the other hand, the energy price is not (fully, at least) decided by regulation. Second, the GenCo the electricity generating company has very much freedom on deciding the location, capacity and timing on new generation sources. Third, the macro-economic and demographic factors are not the only main factor to influence the demand, but the competitors' strategies are a major source of uncertainty. Fourth, the power to be generated by some news RES, mainly wind and, in a lesser extent, solar and photovoltaic sources, is subject to a high uncertainty (that, on the other hand, it is difficult to formulate). Fifth, given the type of new energy sources, there is more variety on the location sites and generation capacity, which allows considering more opportunities for strategic planning. And, sixth, there are other stakeholders (environmentalists, among others) having different goals (whose directions are not the same sense as the GenCoelectricity generating company) that, in some way, have to be considered in the decision making, plus some Government and EC directives, etc. All of that induce to consider multiobjective optimization.

So, the GenCoelectricity generating company's aim has been moved from cost minimization to expected profit maximization along the time horizon. One of the interesting disciplines for problem solving is stochastic optimization, where the uncertainty of the main elements is represented (i.e., quantified) by a finite set of scenarios, ether in a two stage or a multistage scenario tree. Anyway, the problem modeling and algorithm development are big challenges, given the gigantic character of the problem. As an additional difficulty, big GenCos can influence some of the main uncertain parameters in the problem; say the energy price, among others. Then, their the probability and value along the time horizon can be influenced by the decision-maker. In this case, the so-called decision-dependent probabilities [15,18,19] (also called endogenous uncertainty) should be considered. One of the potential tools consists of using stochastic mixed 0-1 quadratic mechanisms; see [10], to be added to the modeling schemes presented next.


The rationale [20] behind a time-consistent risk averse measure is that the solution value to be obtained for the successor set of a give node in the scenario tree for the related time consistent submodel, see [12], 'solved' at the stage to whom the node belongs to, should have the same value as in the original model 'solved' at the beginning of the time horizon. See in [20] and references therein the time consistent version of CVaR (Conditional Value-at-Risk), a very popular risk averse measure.

It is work worth to point out that, by construction, the time-consistent version of risk averse measure does not avoid the risk on non-desired shortfalls on reaching the thresholds for the given functions at intermediate stages of the (long) time horizon for the energy generation expansion planning problem. It is a challenge for problem solving, but both time-consistent and time-inconsistent versions of risk averse measures should be jointly considered in the same model.


[23] M.T. Vespucci, M. Bertocchi, S. Zigrino and L.F. Escudero. Stochastic optimization models for the power generation capacity expansion problem with risk management. doi:10.1109/EEM.2013.6607352. 10th International Conference IEEE on the European Energy Market EEM13, Stockholm (Sweden), 2013.

Optimization methods

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:


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:


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  for big companies the following are the issues of relevance, mainly addressed in the context of market competition:


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.Data and Software


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

[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

[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

Optimization Methods

The GEP can be mathematically formulated as a high dimensional, nonlinear, nonconvex, mix-integer and highly constrained optimization problem with the least cost of the investment as the optimization criterion. The complexity of the problem rapidly increases if many practical constraints are taken into account.

Methods to solve the GEP can be generally categorized into two types: traditional mathematical programming methods and methods based on heuristic techniques. The traditional mathematical methods include dynamic programming (DP), mix-integer programming (MIP), branch and bound, Benders’ decomposition, network flow methods, and others. These methods are usually strict in mathematics, strong in numerical manipulations, weak in handling qualitative constraints, and slower in computational performance [1]. The heuristic techniques mainly include the  application of Artificial Intelligence (AI) approaches, such as GAs, DE, EP, evolutionary strategy (ES), ACO, PSO, TS, SA, and a hybrid approach [2]. The main advantage of the heuristic techniques is their flexibility for handling numerous qualitative constraints that are common in the GEP in the deregulated power industry.

The application of PSO for solving GEP has been reported in the literature [2]–[4]. The application and comparison of metaheuristic techniques to solve the GEP has been presented in [2], where PSO is compared with eight other metaheuristic techniques in terms of the success rate and execution time. The performance of the metaheuristic techniques is improved by the application of a virtual mapping procedure, intelligent initial population generation, and penalty factor approach. Optimal and near-optimal solutions are reached within a reasonable amount of time. In addition, Kannan et al. [5] have presented the application of the PSO technique and its variants to the GEP. In this case, three different test cases are used for comparison with DP. The comparisons are based on computation time, success rate, and error limit. The virtual mapping procedure is also used here. For all test cases, the PSO technique and its variants produce better results in much less time compared with DP. Among the PSO variants, it was observed that the constriction factor approach performed comparatively better.

Additionally, Sensarna et al. [3] have presented the application of PSO to GEP with a parametric approach for planning and transmission expansion including topology optimization, capital expenses, power losses, network security, and revenue. Likewise, Slochanal et al. [4] have presented the application of PSO to the generation expansion planning problem in a competitive environment.

[1] F. Wu, Z. Yen, Y. Hou, and Y. Ni, “Applications of AI techniques to generation planning and investment,” in Proc. IEEE Power Eng. Soc. General Meeting, Jun. 2004, vol. 1, pp. 936–940.

[2] S. Kannan, S. Slochanal, and N. Padhy, “Application and comparison of metaheuristic techniques to generation expansion planning problem,” IEEE Trans. Power Syst., vol. 20, no. 1, pp. 466–475, Feb. 2005.

[3] P. Sensarna, M. Rahmani, and A. Carvalho, “A comprehensive method for optimal expansion planning using particle swarm optimization,” in Proc. IEEE Power Eng. Soc. Winter Meeting 2002, Jan. 2002, vol. 2, pp. 1317–1322.

[4] S. Slochanal, S. Kannan, and R. Rengaraj, “Generation expansion planning in the competitive environment,” in Proc. 2004 Int. Conf. Power Syst. Technol., Nov. 2004, pp. 1546–1549.

[5] S. Kannan, S. Slochanal, and N. Padhy, “Application of particle swarm optimization technique and its variants to generation expansion problem,” ELSERVIER Electric Power Syst. Res., vol. 70, no. 3, pp. 203–210, Aug. 2004

Data and Software

On the software side, general purpose stochastic optimization software still seems far away. Planning models are highly problem oriented and off-the-shelf packages are not available. Companies use modeling languages like GAMS, AMPL, AIMMS, Python together with standard solvers to develop problem specific approaches.


Prof. Laureano Escudero, Universidad Rey Juan Carlos

Dr Alireza Soroudi, University College Dublin (UCD)

Prof. Christoph Helmberg, TU Chemnitz

Dr. Željko Kanović, University of Novi Sad