Page tree
Skip to end of metadata
Go to start of metadata

You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 2 Next »

One of the major and difficult problems in the energy area that the European Union (EU) is facing today consists of estimating the timing for clean power generation technologies and electricity transmission expansion network at a pan-European level in a long term (e.g., 30 years time horizon). EU has established aggressive pollutant emission reduction targets: a 20% (res. 27%) reduction in greenhouse gases with respect to 1990 levels by 2020 (res. 2030) and an objective of 80% reduction by 2050.  See {www.epp.eurostat.}.

Mathematical optimization models and algorithms for problem solving to address the above challenges in the electricity open market [14] are essential computerized tools for helping in the decision making for estimating the following key issues: Feasible type and mix of power generation sources, ranging from less coal, nuclear and combined cycle gas turbine to more renewable energy sources (RES), namely hydroelectric, wind, solar, photovoltaic and biomass, among others;  and timing for power generation plant / farm site locations and dimensions. The solution should maximize different types of utility criteria and quantifying the benefits of using cleaner, safer and efficient (cheaper) energy.

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 (GenCos) have a reduced decision-making on generation expansion capacity planning. The energy prices where 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 are needed to provide solutions to help the decision-making could not be considered.

However, today the situation has drastically changed. The HW/SW computer power capability is very high, and it seems that its exponential growth will continue in the near future, at least. 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 has very much freedom on deciding the location, capacity and timing on news 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 sources (and, in a lesser extent, solar and photovoltaic ones) 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, what allow considering more opportunities for strategic planning. And, sixth, there are other stakeholders (environmentalists, among others) having different goals (whose directions are not in the same sense as the GenCo) 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 GenCo'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 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.

Multistage stochastic mixed 0-1 optimization modeling for risk management should be considered. There are different approaches (some of them very recent ones) for energy generation planning, see [1,2,7,13,21,22,23], among others. The main parameters in the problem are uncertain and, so, a set of scenarios should be generated by considering the realization of the following parameters, at least: Availability (and price, in case) of raw material for power generation: gas, fuel, water, wind, solar, etc.;Electricity demand and prices at focal nodes in the energy network; Operating hours per period of power generation technologies;  CO2 emission permits;  Green Certificates prices for buying and selling in the market, and allowed bounds; Power generation costs of different technologies; Electricity loss of candidate power generation technologies; Investment allocation bounding of the cost for the total power generation.

There is not a unique function-criterion to consider. Rather, it is a multicriteria problem, since the model considers the maximization of the NPV of the expected profit of the investment and consumer stakeholders’ goals over the scenarios along the time horizon, subject to risk reduction of the negative impact of the solution to be provided by the optimization system in non-wanted scenarios, plus utility objectives of other stakeholders. Those other objectives include the power share of cleaner, safer and efficient energy accessible to all consumption nodes, cost investment from private and public institutions, generation network reliability, EC directives and EU Governments on environmental issues and others.

One of the difficult problems to deal with is the generation of a set of scenarios to represent the realization of the uncertainty as structured in a multistage scenario tree.  Hence, a node in the tree for a given stage is related (in a one-to-one correspondence) to a group of scenarios that up to the stage have the same values in the uncertain parameters. Then, the solution for those scenarios should be unique for all stages up to the stage where the node in the tree belongs to, i.e., the so-named nonanticipativity principle is satisfied.

In the so-called Risk Neutral approach (RN), the function to maximize consists of the NPV of the expected  profit along the time horizon over the scenarios with the following elements related to a given GenCo the energy network: Revenue from sale of electricity, revenue from sale (or, alternatively, cost from purchase) of Green Certificates, penalization of CO2 emissions, variable generation cost of thermal power plants,  variable generation cost of renewable energy source power plants / farms (wind, solar, photovoltaic, biomass, etc.), periodic debt repayment of the investment on the new power plants / farms and new hydro power turbines, fixed power generation cost of available new plants / farms and new hydro power turbines,  etc.

The gigantic character of the problem can be assessed by considering its dynamic setting (say, 30 years time horizon), the number and dimensions of replicated networks (i.e., hyper hydro valleys) in the time horizon for some big generator companies (e.g., EdF has 20+ valleys, some with 50+ elements, see [4], multiple choices in time and space of location and capacity decisions for the energy generation system of the given GenC0 (current and candidate power generation plants / farms), and the representative scenario tree to consider for the uncertain parameters.

The aim of the Risk Neutral type model performs the maximization of the NPV of the expected profit. The main drawback of this popular strategy is that it ignores the variability of the profit over the scenarios, in particular the “left” tail of the profits of the non-wanted scenarios. For the problems with so high variability, there are some risk averse approaches that, additionally, deal with risk management. Among then, the so-called time-inconsistent stochastic dominance (TSD) measure reduces the risk of the negative impact of the solution in non-wanted scenarios in a better way than others under some circumstances. See [3] for a computational comparison of some risk averse strategies, see also [5].

The TSD measure presented in [9]  for stochastic problems as a mixture of first- and second-order stochastic dominance strategies. It is a multistage extension of the two-stage strategies introduced in [16,17], plus the consideration of hedging the solution against some types of negative impacts in non-wanted scenarios at selected stages along the given time horizon.

Then, the maximization of the NPV of the expected profit is subject to a scheme for risk management that consists of appending to the model  a set of  TSD constraints for given profiles at a stage subset for each function (including the objective one), such that a profile is given by the 4-tupla: Threshold on the function value; maximum target shortfall on reaching the threshold that is allowed for each node in the scenario tree related to any of those stages; bound target on the probability of failure on reaching the threshold; and bound target on the expected shortfall.

As an alternative, the time consistent strategy proposed in [12] is so-called the expected stochastic dominance (ESD) measure. In ESD, however, the profiles are associated with the nodes of a modeler-driven stage subset for each function, where a profile consists of the 4-tupla:  Threshold of the function to be satisfied by any scenario in the group with one-to-one correspondence to the node; maximum shortfall of the value of the function that is allowed for any of those scenarios; upper bound target on the expected deficit (shortfall) on reaching the threshold that is allowed for that group of scenarios; and upper bound on the probability of failing to satisfy the threshold.

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 (Condition, a very popular risk averse measure.

It is work 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 consider in the same model.

The gigantic but well structured multicriteria multistage stochastic nonlinear mixed integer (SMINO) problem with risk management cannot be solved up to optimality, see [8], such that a realistic approach could consist of a combination of the following elements:  Sample scenario schemes, iterative algorithms for solving SMINO by sequential mixed 0- linear one; node-based decomposition algorithms; stochastic mixed 0-1 bilinear optimization solvers; and high performance computing. See in [11] a review of decomposition algorithms for multistage stochastic problem solving.


 [1] W. van Ackooij, R. Henrion, A. Moelle and, R. Zorgati. Joint chance constrained programming for hydro reservoir management. Optimization Engineering, 15:509-531, 2014.

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

[3] A. Alonso-Ayuso, F. Carvallo, L.F. Escudero, M. Guignard, J. Pi, and R. Puranmalka, A. Weintraub. On the optimization of copper extraction in mining under uncertainty in copper prices. European Journal of Operational Research, 233:711-726, 2014.

[4] S. Charousset. A review of the main mixed-integer nonlinear optimization problems regarding electricity generation management at Electricite de France. Cost Workshop on Mixed-Integer NonLinear Programming. EC Cost Action TD1207, Paris, 2013.

[5] A.J. Conejo, M. Carrion and J.M. Morales. Decision making under uncertainty in electricity markets. Springer, 2010.

[6] G. Emiel and C. Sagastizabal. Incremental like bundle methods with applications to energy planning. Computational Optimization and Applications, 46:305-332, 2009.

[7] L.F. Escudero, J.L. de la Fuente, C. Garcia and F.J. Prieto, Hydropower generation management under uncertainty via scenario analysis and parallel computation. IEEE Transactions on Power Systems, 11:683-690, 1996.

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

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

[10] L.F Escudero, A. Garin, M. Merino and G. Perez. On multistage mixed 0-1 optimization under a mixture of Exogenous and Endogenous Uncertainty in a risk averse environment Mini-symposium on Exogenous and Endogenous uncertainty in Stochastic Programming. 13h Tri-annual International Conferecne on Stochastic Programming (ICSP). Bergamo (Italy), 2013.

[11] L.F Escudero, A. Garin and A. Unzueta. Cluster Lagrangean decomposition for time stochastic dominance induced by mixed integer-linear recourse in multistage stochastic optimization. Submitted.

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

[13] L.F. Escudero, I. Paradinas, J. Salmeron and M. Sanchez, SEGEM: A Simulation approach for Electric Generation Management. IEEE Transactions on Power Systems, 13:738-748, 1998.

[14] L.F. Escudero and M.V.F. Pereira. New trends and OR/MS opportunities in the electricity open market. OR/MS Today, 27,2:42-46, 2000.

[15] V. Goel and  I. Grossmann. A class of stochastic programs with decision dependent uncertainty. Mathematical Programming, 108: 355-294, 2006.

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

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

[18] V. Gupta and I.E. Grossmann. Solution strategies for multistage stochastic programming with endogenous uncertainties. Computers & Chemical Engineering, 35:2235-2247, 2011.

[19] L. Hellemo, P.I. Barton and A. Tomasgard Stochastic Programming with Decision-Dependent Probabilities. Submitted.

[20] T. Homem-de-Mello and  B.K. Pagnoncelli. Risk aversion in multistage stochastic programming: A modeling and algorithmic perspective. European Journal of Operational Research, 249:188-199, 2016.

[21] M.V.F. Pereira and L.M.V.G. Pinto.. Multi-stage stochastic optimization applied to energy planning. Mathematical Programming, 52:359-375, 1991.

[22] C. Sagastizabal. Divide to conquer: Decomposition methods for energy optimization. Mathematical Programming Ser. B, 134:187-222, 2012.

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



  • No labels