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 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 (electricity 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 hardware/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 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 electricity 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 electricity 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, 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.
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 GenCo (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 them, 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 (Conditional Value-at-Risk), a very popular risk averse measure.
It is 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.
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.
References
[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. http://minlp.cheme.cmu.edu/2014/index.html. 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
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
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.
Contributors:
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
