Top

Optimization and Engineering

Published in:

16-10-2019 | Research Article

Electric power infrastructure planning under uncertainty: stochastic dual dynamic integer programming (SDDiP) and parallelization scheme

Authors: Cristiana L. Lara, John D. Siirola, Ignacio E. Grossmann

Published in: Optimization and Engineering | Issue 4/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We address the long-term planning of electric power infrastructure under uncertainty. We propose a Multistage Stochastic Mixed-integer Programming formulation that optimizes the generation expansion to meet the projected electricity demand over multiple years while considering detailed operational constraints, intermittency of renewable generation, power flow between regions, storage options, and multiscale representation of uncertainty (strategic and operational). To be able to solve this large-scale model, which grows exponentially with the number of stages in the scenario tree, we decompose the problem using Stochastic Dual Dynamic Integer Programming (SDDiP). The SDDiP algorithm is computationally expensive but we take advantage of parallel processing to solve it more efficiently. The proposed formulation and algorithm are applied to a case study in the region managed by the Electric Reliability Council of Texas for scenario trees considering natural gas price and carbon tax uncertainty for the reference case, and a hypothetical case without nuclear power. We show that the parallelized SDDiP algorithm allows in reasonable amounts of time the solution of multistage stochastic programming models of which the extensive form has quadrillions of variables and constraints.

next article A performance-based design framework for enhancing decision-making at the conceptual phase of a motorcycle rear suspension development

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

In this paper we do not consider hydroelectric power as it is available in very limited amounts in the ERCOT region.

\(DIC_{i,t}\) is used in the calculation for the life extension investment cost, which is in terms of a fraction \(LE_i\) of the capital cost. Therefore the investment cost for the existing cluster is approximated as being the same as for the potential clusters that have the same or similar generation technology.

All the costs are in 2015 USD.

Albornoz VM, Benario P, Rojas ME (2004) A two-stage stochastic integer programming model for a thermal power system expansion. Int Trans Oper Res 11(3):243–257. https://doi.org/10.1111/j.1475-3995.2004.00456.xCrossRefMATH

Babatunde OM, Munda JL, Hamam Y (2018) Generation expansion planning: a survey. In: 2018 IEEE PES/IAS PowerAfrica, pp 307–312

Baringo L, Baringo A (2018) A stochastic adaptive robust optimization approach for the generation and transmission expansion planning. IEEE Trans Power Syst 33(1):792–802. https://doi.org/10.1109/TPWRS.2017.2713486CrossRef

Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math Program 99(2):351–376. https://doi.org/10.1007/s10107-003-0454-yMathSciNetCrossRefMATH

Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35–53. https://doi.org/10.1287/opre.1030.0065MathSciNetCrossRefMATH

Birge JR (1985) Decomposition and partitioning methods for multistage stochastic linear programs. Oper Res 33(5):989–1007. https://doi.org/10.1287/opre.33.5.989MathSciNetCrossRefMATH

Birge JR, Louveaux F (2011) Introduction to stochastic programming, 2nd edn. Springer, BerlinCrossRef

Bruno S, Ahmed S, Shapiro A, Street A (2016) Risk neutral and risk averse approaches to multistage renewable investment planning under uncertainty. Eur J Oper Res 250(3):979–989. https://doi.org/10.1016/j.ejor.2015.10.013MathSciNetCrossRefMATH

Care CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper Res Lett 24(1):37–45. https://doi.org/10.1016/S0167-6377(98)00050-9MathSciNetCrossRefMATH

Cerisola S, Baillo A, Fernandez-Lopez JM, Ramos A, Gollmer R (2009) Stochastic power generation unit commitment in electricity markets: a novel formulation and a comparison of solution methods. Oper Res 57(1):32–46. https://doi.org/10.1287/opre.1080.0593CrossRefMATH

Chandra R, Dagum L, Kohr D, Maydan D, McDonald J, Menon R (2001) Parallel programming in OpenMP. Morgan Kaufmann Publishers Inc., San Francisco

Chen C, Li Y, Huang G, Li Y (2012) A robust optimization method for planning regional-scale electric power systems and managing carbon dioxide. Int J Electr Power Energy Syst 40(1):70–84. https://doi.org/10.1016/j.ijepes.2012.02.007CrossRef

Denholm P, O’Connell M, Brinkman G, Jorgenson J (2015) Overgeneration from solar energy in California. In: A field guide to the duck chart. https://doi.org/10.2172/1226167

Dentcheva D, Römisch W (1998) Optimal power generation under uncertainty via stochastic programming. In: Marti K, Kall P (eds) Stochastic programming methods and technical applications. Springer, Berlin, pp 22–56CrossRef

de Queiroz AR, Morton DP (2013) Sharing cuts under aggregated forecasts when decomposing multi-stage stochastic programs. Oper Res Lett 41(3):311–316. https://doi.org/10.1016/j.orl.2013.03.003MathSciNetCrossRefMATH

Diamant A (2017) The electric generation expansion analysis system (EGEAS) software. Technical reports. Electric Power Research Institute

Ding J, Somani A (2010) A long-term investment planning model for mixed energy infrastructure integrated with renewable energy. In: 2010 IEEE green technologies conference, pp 1–10. https://doi.org/10.1109/GREEN.2010.5453785

EIA: Annual Energy Outlook 2019. Technical reports, U.S. Energy Information Administration (2019). https://www.eia.gov/outlooks/aeo/pdf/aeo2019.pdf

Flores-Quiroz A, Palma-Behnke R, Zakeri G, Moreno R (2016) A column generation approach for solving generation expansion planning problems with high renewable energy penetration. Electr Power Syst Res 136:232–241. https://doi.org/10.1016/j.epsr.2016.02.011CrossRef

Frangioni A (2005) About lagrangian methods in integer optimization. Ann Oper Res 139(1):163–193. https://doi.org/10.1007/s10479-005-3447-9MathSciNetCrossRefMATH

Gacitua L, Gallegos P, Henriquez-Auba R, Lorca A, Negrete-Pincetic M, Olivares D, Valenzuela A, Wenzel G (2018) A comprehensive review on expansion planning: models and tools for energy policy analysis. Renew Sustain Energy Rev 98:346–360. https://doi.org/10.1016/j.rser.2018.08.043CrossRef

Gandulfo W, Gil E, Aravena I (2014) Generation capacity expansion planning under demand uncertainty using stochastic mixed-integer programming. In: 2014 IEEE PES general meeting|conference exposition, pp 1–5. https://doi.org/10.1109/PESGM.2014.6939368

Gil E, Aravena I, Crdenas R (2015) Generation capacity expansion planning under hydro uncertainty using stochastic mixed integer programming and scenario reduction. IEEE Trans Power Syst 30(4):1838–1847. https://doi.org/10.1109/TPWRS.2014.2351374CrossRef

Gorenstin BG, Campodonico NM, Costa JP, Pereira MVF (1993) Power system expansion planning under uncertainty. IEEE Trans Power Syst 8(1):129–136. https://doi.org/10.1109/59.221258CrossRef

Grossmann IE, Apap RM, Calfa BA, Garca-Herreros P, Zhang Q (2016) Recent advances in mathematical programming techniques for the optimization of process systems under uncertainty. Comput Chem Eng 91:3–14. https://doi.org/10.1016/j.compchemeng.2016.03.002CrossRef

Gupta V, Grossmann IE (2014) A new decomposition algorithm for multistage stochastic programs with endogenous uncertainties. Comput Chem Eng 62:62–79. https://doi.org/10.1016/j.compchemeng.2013.11.011CrossRef

Gurobi Optimization L (2018) Gurobi optimizer reference manual. http://www.gurobi.com

Helseth A, Braaten H (2015) Efficient parallelization of the stochastic dual dynamic programming algorithm applied to hydropower scheduling. Energies 8(12):14287–14297. https://doi.org/10.3390/en81212431CrossRef

Heuberger CF, Rubin ES, Staffell I, Shah N, Dowell NM (2017) Power capacity expansion planning considering endogenous technology cost learning. Appl Energy 204:831–845. https://doi.org/10.1016/j.apenergy.2017.07.075CrossRef

Homem-de Mello T, de Matos VL, Finardi EC (2011) Sampling strategies and stopping criteria for stochastic dual dynamic programming: a case study in long-term hydrothermal scheduling. Energy Syst 2(1):1–31. https://doi.org/10.1007/s12667-011-0024-yCrossRef

Huang K, Ahmed S (2009) The value of multistage stochastic programming in capacity planning under uncertainty. Oper Res 57(4):893–904MathSciNetCrossRef

IEEFA: Indias electricity sector transformation. Technical reports, Institute for Energy Economics and Financial Analysis (2017). http://ieefa.org/wp-content/uploads/2017/11/India-Electricity-Sector-Transformation_Nov-2017-3.pdf

Infanger G, Morton DP (1996) Cut sharing for multistage stochastic linear programs with interstage dependency. Math Program 75(2):241–256. https://doi.org/10.1007/BF02592154MathSciNetCrossRefMATH

Jin S, Ryan SM, Watson JP, Woodruff DL (2011) Modeling and solving a large-scale generation expansion planning problem under uncertainty. Energy Syst 2(3):209–242. https://doi.org/10.1007/s12667-011-0042-9CrossRef

Jin S, Botterud A, Ryan SM (2014) Temporal versus stochastic granularity in thermal generation capacity planning with wind power. IEEE Trans Power Syst 29(5):2033–2041. https://doi.org/10.1109/TPWRS.2014.2299760CrossRef

Kaut M, Midthun KT, Werner AS, Tomasgard A, Hellemo L, Fodstad M (2014) Multi-horizon stochastic programming. Comput Manag Sci 11(1):179–193. https://doi.org/10.1007/s10287-013-0182-6MathSciNetCrossRefMATH

Kim K, Zavala VM (2018) Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs. Math Program Comput 10(2):225–266. https://doi.org/10.1007/s12532-017-0128-zMathSciNetCrossRefMATH

Koltsaklis N, Georgiadis M (2015) A multi-period, multi-regional generation expansion planning model incorporating unit commitment constraints. Appl Energy 158:310–331. https://doi.org/10.1016/j.apenergy.2015.08.054CrossRef

Koltsaklis NE, Dagoumas AS (2018) State-of-the-art generation expansion planning: a review. Appl Energy 230:563–589. https://doi.org/10.1016/j.apenergy.2018.08.087CrossRef

Lara CL (2019) Sddip implementation for a generation expansion planning model. https://github.com/cristianallara/SDDiP

Lara CL, Mallapragada DS, Papageorgiou DJ, Venkatesh A, Grossmann IE (2018a) Deterministic electric power infrastructure planning: mixed-integer programming model and nested decomposition algorithm. Eur J Oper Res 271(3):1037–1054. https://doi.org/10.1016/j.ejor.2018.05.039MathSciNetCrossRefMATH

Lara CL, Omell B, Miller D, Grossmann IE (2018b) Expanding the scope of electric power infrastructure planning. In: Eden MR, Ierapetritou MG, Towler GP (eds.) 13th international symposium on process systems engineering (PSE 2018), Computer aided chemical engineering, vol 44. Elsevier, Amsterdam, pp 1309–1314. https://doi.org/10.1016/B978-0-444-64241-7.50213-5

Lassner C (2018) pymp. https://github.com/classner/pymp

Li S (2014) Robust optimization of electric power generation expansion planning considering uncertainty of climate change. Ph.D. thesis, Rutgers, The State University of New Jersey

Li S, Coit D, Selcuklu S, Felder F (2014) Electric power generation expansion planning: robust optimization considering climate change. In: IIE annual conference and Expo 2014, pp 1049–1058

Liu Y, Sioshansi R, Conejo AJ (2018) Multistage stochastic investment planning with multiscale representation of uncertainties and decisions. IEEE Trans Power Syst 33(1):781–791. https://doi.org/10.1109/TPWRS.2017.2694612CrossRef

Lohmann T, Rebennack S (2017) Tailored benders decomposition for a long-term power expansion model with short-term demand response. Manag Sci 63(6):2027–2048. https://doi.org/10.1287/mnsc.2015.2420CrossRef

Lohmann T, Hering AS, Rebennack S (2016) Spatio-temporal hydro forecasting of multireservoir inflows for hydro-thermal scheduling. Eur J Oper Res 255(1):243–258. https://doi.org/10.1016/j.ejor.2016.05.011MathSciNetCrossRefMATH

Lopez JA, Ponnambalam K, Quintana VH (2007) Generation and transmission expansion under risk using stochastic programming. IEEE Trans Power Syst 22(3):1369–1378. https://doi.org/10.1109/TPWRS.2007.901741CrossRef

Loulou R, Goldstein G, Noble K (2004) Documentation for the MARKAL family of models. Technical reports. International Energy Agency

Loulou R, Remne U, Kanudia A, Lehtila A, Goldstein G (2005) Documentation for the TIMES Model—part I. Technical reports. International Energy Agency

Luo X, Wang J, Dooner M, Clarke J (2015) Overview of current development in electrical energy storage technologies and the application potential in power system operation. Appl Energy 137:511–536. https://doi.org/10.1016/j.apenergy.2014.09.081CrossRef

Malcolm SA, Zenios SA (1994) Robust optimization for power systems capacity expansion under uncertainty. J Oper Res Soc 45(9):1040–1049CrossRef

Mallapragada DS, Papageorgiou DJ, Venkatesh A, Lara CL, Grossmann IE (2018) Impact of model resolution on scenario outcomes for electricity sector system expansion. Energy 163:1231–1244. https://doi.org/10.1016/j.energy.2018.08.015CrossRef

Mejia-Giraldo D (2013) Robust and flexible planning of power system generation capacity. Ph.D. thesis, Iowa State University

Meja-Giraldo D, McCalley JD (2014) Maximizing future flexibility in electric generation portfolios. IEEE Trans Power Syst 29(1):279–288. https://doi.org/10.1109/TPWRS.2013.2280840CrossRef

Moreira A, Pozo D, Street A, Sauma E (2017) Reliable renewable generation and transmission expansion planning: co-optimizing system’s resources for meeting renewable targets. IEEE Trans Power Syst 32(4):3246–3257. https://doi.org/10.1109/TPWRS.2016.2631450CrossRef

Mulvey JM, Ruszczyski A (1995) A new scenario decomposition method for large-scale stochastic optimization. Oper Res 43(3):477–490. https://doi.org/10.1287/opre.43.3.477MathSciNetCrossRefMATH

Mulvey JM, Vanderbei RJ, Zenios SA (1995) Robust optimization of large-scale systems. Oper Res 43(2):264–281. https://doi.org/10.1287/opre.43.2.264MathSciNetCrossRefMATH

Munoz FD, Watson JP (2015) A scalable solution framework for stochastic transmission and generation planning problems. Comput Manag Sci 12(4):491–518. https://doi.org/10.1007/s10287-015-0229-yMathSciNetCrossRefMATH

O’Neill RP, Krall EA, Hedman KW, Oren SS (2013) A model and approach to the challenge posed by optimal power systems planning. Math Program 140(2):239–266. https://doi.org/10.1007/s10107-013-0695-3MathSciNetCrossRefMATH

Oree V, Sayed Hassen S, Fleming P (2017) Generation expansion planning optimisation with renewable energy integration: a review. Renew Sustain Energy Rev 69:790–803. https://doi.org/10.1016/j.rser.2016.11.120CrossRef

Palmintier B, Webster M (2011) Impact of unit commitment constraints on generation expansion planning with renewables. In: 2011 IEEE power and energy society general meeting, pp 1–7. https://doi.org/10.1109/PES.2011.6038963

Palmintier B, Webster M (2014) Heterogeneous unit clustering for efficient operational flexibility modeling. In: 2014 IEEE PES general meeting|conference exposition, pp. 1–1. https://doi.org/10.1109/PESGM.2014.6939001

Park H, Baldick R (2016) Multi-year stochastic generation capacity expansion planning under environmental energy policy. Appl Energy 183:737–745. https://doi.org/10.1016/j.apenergy.2016.08.164CrossRef

Pereira MVF, Pinto LMVG (1985) Stochastic optimization of a multireservoir hydroelectric system: a decomposition approach. Water Resour Res 21(6):779–792. https://doi.org/10.1029/WR021i006p00779CrossRef

Pereira MVF, Pinto LMVG (1991) Multi-stage stochastic optimization applied to energy planning. Math Program 52(1):359–375. https://doi.org/10.1007/BF01582895MathSciNetCrossRefMATH

Philpott A, Guan Z (2008) On the convergence of stochastic dual dynamic programming and related methods. Oper Res Lett 36(4):450–455. https://doi.org/10.1016/j.orl.2008.01.013MathSciNetCrossRefMATH

Pina A, Silva CA, Ferro P (2013) High-resolution modeling framework for planning electricity systems with high penetration of renewables. Appl Energy 112:215–223. https://doi.org/10.1016/j.apenergy.2013.05.074CrossRef

Pinto RJ, Borges CT, Maceira MEP (2013) An efficient parallel algorithm for large scale hydrothermal system operation planning. IEEE Trans Power Syst 28(4):4888–4896. https://doi.org/10.1109/TPWRS.2012.2236654CrossRef

Poncelet K, Delarue E, Duerinck J, Six D, D’haeseleer W (2014) The importance of integrating the variability of renewables in long-term energy planning models. KU Leuven, Leuven, pp 1–18

Pozo D, Contreras J, Sauma EE (2014) Unit commitment with ideal and generic energy storage units. IEEE Trans Power Syst 29(6):2974–2984. https://doi.org/10.1109/TPWRS.2014.2313513CrossRef

Rachev ST, Roemisch W (2002) Quantitative stability in stochastic programming: the method of probability metrics. Math Oper Res 27(4):792–818MathSciNetCrossRef

Rebennack S (2014) Generation expansion planning under uncertainty with emissions quotas. Electr Power Syst Res 114:78–85. https://doi.org/10.1016/j.epsr.2014.04.010CrossRef

Rebennack S (2016) Combining sampling-based and scenario-based nested benders decomposition methods: application to stochastic dual dynamic programming. Math Program 156(1–2):343–389. https://doi.org/10.1007/s10107-015-0884-3MathSciNetCrossRefMATH

Rebennack S, Flach B, Pereira MVF, Pardalos PM (2012) Stochastic hydro-thermal scheduling under \(\text{CO}_{2}\)emissions constraints. IEEE Trans Power Syst 27(1):58–68. https://doi.org/10.1109/TPWRS.2011.2140342CrossRef

Sadeghi H, Rashidinejad M, Abdollahi A (2017) A comprehensive sequential review study through the generation expansion planning. Renew Sustain Energy Rev 67:1369–1394. https://doi.org/10.1016/j.rser.2016.09.046CrossRef

Schmidt O, Hawkes A, Gambhir A, Staffell I (2017) The future cost of electrical energy storage based on experience rates. Nat Energy 6:17110. https://doi.org/10.1038/nenergy.2017.110CrossRef

Shapiro A, Tekaya W, Costa JPd, Soares MP (2013) Risk neutral and risk averse stochastic dual dynamic programming method. Eur J Oper Res 224(2):375–391. https://doi.org/10.1016/j.ejor.2012.08.022MathSciNetCrossRefMATH

Short W, Sullivan P, Mai T, Mowers M, Uriarte C, Blair N, Heimiller D, Martinez A (2011) Regional energy deployment system (ReEDS). Technical reports. National Renewable Energy Laboratory (NREL)

Shortt A, O’Malley M (2010) Impact of variable generation in generation resource planning models. In: IEEE PES general meeting, pp 1–6. https://doi.org/10.1109/PES.2010.5589461

Thome F, Pereira M, Granville S, Fampa M (2013) Non-convexities representation on hydrothermal operation planning using sddp, pp 1–9 (unpublished)

Union of concerned scientists: the nuclear power Dilemma. Technical reports, Union of Concerned Scientists (2018). https://www.ucsusa.org/sites/default/files/attach/2018/11/Nuclear-Power-Dilemma-executive-summary.pdf

Watson JP, Woodruff DL (2011) Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. Comput Manag Sci 8(4):355–370. https://doi.org/10.1007/s10287-010-0125-4MathSciNetCrossRefMATH

Wogrin S, Centeno E, Barquin J (2011) Generation capacity expansion in liberalized electricity markets: a stochastic mpec approach. IEEE Trans Power Syst 26(4):2526–2532. https://doi.org/10.1109/TPWRS.2011.2138728CrossRef

Zhan Y, Zheng QP, Wang J, Pinson P (2017) Generation expansion planning with large amounts of wind power via decision-dependent stochastic programming. IEEE Trans Power Syst 32(4):3015–3026. https://doi.org/10.1109/TPWRS.2016.2626958CrossRef

Zhang Q, Grossmann IE, Lima RM (2016) On the relation between flexibility analysis and robust optimization for linear systems. AIChE J 62(9):3109–3123. https://doi.org/10.1002/aic.15221CrossRef

Zou J, Ahmed S, Sun XA (2018a) Partially adaptive stochastic optimization for electric power generation expansion planning. INFORMS J Comput 30(2):388–401. https://doi.org/10.1287/ijoc.2017.0782MathSciNetCrossRef

Zou J, Ahmed S, Sun XA (2018b) Stochastic dual dynamic integer programming. Math Program. https://doi.org/10.1007/s10107-018-1249-5CrossRefMATH

Title: Electric power infrastructure planning under uncertainty: stochastic dual dynamic integer programming (SDDiP) and parallelization scheme
Authors: Cristiana L. Lara
John D. Siirola
Ignacio E. Grossmann
Publication date: 16-10-2019
Publisher: Springer US
Published in: Optimization and Engineering / Issue 4/2020
Print ISSN: 1389-4420
Electronic ISSN: 1573-2924
DOI: https://doi.org/10.1007/s11081-019-09471-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 4/2020

A game-theoretic optimisation approach to fair customer allocation in oligopolies

Gradient based biobjective shape optimization to improve reliability and cost of ceramic components

Using interior point solvers for optimizing progressive lens models with spherical coordinates

Optimization of covered calls under uncertainty

A performance-based design framework for enhancing decision-making at the conceptual phase of a motorcycle rear suspension development

Numerical simulation of base-isolated buildings in collisions with surrounding moat walls during earthquakes: a nonsmooth mechanics approach

Premium Partners