Lagrangian decomposition for stochastic TIMES energy system optimization model

Yujun Zhu; Ju Ming; Yujun Zhu; Ju Ming

doi:10.3934/math.2022445

AIMS Mathematics

2022, Volume 7, Issue 5: 7964-7996. doi: 10.3934/math.2022445

Previous Article Next Article

Research article Special Issues

Lagrangian decomposition for stochastic TIMES energy system optimization model

Yujun Zhu ^1,2,
Ju Ming ^{1
,
,}

1.
School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan, China
2.
School of Mathematics, University of Edinburgh, Edinburgh, U.K

Received: 26 October 2021 Revised: 16 January 2022 Accepted: 09 February 2022 Published: 22 February 2022
MSC : 49N15, 90C15

Energy system optimization models play an essential role in current decision support on topics including energy security, sustainable development and environmental protection from industrial, regional, national and even global perspective. One of the key energy system optimization models applied in international energy policy is TIMES. The article establishes two basic deterministic TIMES models which cover an energy commodity (coal or gas), a three-step supply curve and an end-use energy service demand. Then we convert the deterministic TIMES models into a stochastic optimization problem with multiple scenarios, and implement the Lagrangian decomposition approach in solving the stochastic programming models. The numerical experiment shows the feasibility of the Lagrangian decomposition algorithm to solve stochastic TIMES models with a small amount of scenarios, and analyze several reasons for non-convergence cases including the choice of step length and initial values of Lagrangian multipliers.
- the TIMES model,
- stochastic extension,
- two-stage stochastic programs with recourse,
- scenario decomposition,
- Lagrangian relaxation,
- supergradient ascent method
Citation: Yujun Zhu, Ju Ming. Lagrangian decomposition for stochastic TIMES energy system optimization model[J]. AIMS Mathematics, 2022, 7(5): 7964-7996. doi: 10.3934/math.2022445

Related Papers:

Abstract

Energy system optimization models play an essential role in current decision support on topics including energy security, sustainable development and environmental protection from industrial, regional, national and even global perspective. One of the key energy system optimization models applied in international energy policy is TIMES. The article establishes two basic deterministic TIMES models which cover an energy commodity (coal or gas), a three-step supply curve and an end-use energy service demand. Then we convert the deterministic TIMES models into a stochastic optimization problem with multiple scenarios, and implement the Lagrangian decomposition approach in solving the stochastic programming models. The numerical experiment shows the feasibility of the Lagrangian decomposition algorithm to solve stochastic TIMES models with a small amount of scenarios, and analyze several reasons for non-convergence cases including the choice of step length and initial values of Lagrangian multipliers.

References

[1]	A. Agra, C. Requejo, F. Rodrigues, An adjustable sample average approximation algorithm for the stochastic production-inventory-routing problem, Networks, 72 (2018), 5–24. https://doi.org/10.1002/net.21796 doi: 10.1002/net.21796
[2]	I. Aravena, A. Papavasiliou, Asynchronous Lagrangian scenario decomposition, Math. Program. Comput., 13 (2021), 1–50. https://doi.org/10.1007/s12532-020-00185-4 doi: 10.1007/s12532-020-00185-4
[3]	O. Balyk, K. S Andersen, S. Dockweiler, M. Gargiulo, K. Karlsson, R. Næraa, et al., TIMES-DK: technology-rich multi-sectoral optimisation model of the Danish energy system, Energy Strategy Rev., 23 (2019), 13–22. https://doi.org/10.1016/j.esr.2018.11.003 doi: 10.1016/j.esr.2018.11.003
[4]	J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4 (1962), 238–252.
[5]	A. Berkelaar, C. Dert, B. Oldenkamp, S. Zhang, A primal-dual decomposition-based interior point approach to two-stage stochastic linear programming, Oper. Res., 50 (2002), 904–915. https://doi.org/10.1287/opre.50.5.904.360 doi: 10.1287/opre.50.5.904.360
[6]	J. R. Birge, F. V. Louveaux, A multicut algorithm for two-stage stochastic linear programs, Eur. J. Oper. Res., 34 (1988), 384–392. https://doi.org/10.1016/0377-2217(88)90159-2 doi: 10.1016/0377-2217(88)90159-2
[7]	C. Böhringer, The synthesis of bottom-up and top-down in energy policy modeling, Energy Econ., 20 (1998), 233–248. https://doi.org/10.1016/S0140-9883(97)00015-7 doi: 10.1016/S0140-9883(97)00015-7
[8]	S. S. Dey, M. Molinaro, Q. Wang, Analysis of sparse cutting planes for sparse MILPs with applications to stochastic MILPs, Math. Oper. Res., 43 (2018), 304–332. https://doi.org/10.1287/moor.2017.0866 doi: 10.1287/moor.2017.0866
[9]	S. Di Leo, F. Pietrapertosa, S. Loperte, M. Salvia, C. Cosmi, Energy systems modelling to support key strategic decisions in energy and climate change at regional scale, Renew. Sust. Energy Rev., 42 (2015), 394–414. https://doi.org/10.1016/j.rser.2014.10.031 doi: 10.1016/j.rser.2014.10.031
[10]	R. K. Dutkiewicz, International symposium on electricity, health and the environment, Cap Town: Energy Research Institute, University of Cape Town, 1995.
[11]	L. F. Escudero, M. Garın, G. Perez, A. Unzueta, Lagrangian decomposition for large-scale two-stage stochastic mixed 0-1 problems, Top, 20 (2012), 347–374. https://doi.org/10.1007/s11750-011-0237-1 doi: 10.1007/s11750-011-0237-1
[12]	X. Feng, S. Di Cairano, R. Quirynen, Inexact adjoint-based SQP algorithm for real-time stochastic nonlinear MPC, IFAC-PapersOnLine, 53 (2020), 6529–6535. https://doi.org/10.1016/j.ifacol.2020.12.068 doi: 10.1016/j.ifacol.2020.12.068
[13]	Y. Fu, G. Huang, L. Liu, M. Zhai, A factorial CGE model for analyzing the impacts of stepped carbon tax on Chinese economy and carbon emission, Sci. Total Environ., 759 (2021), 143512. https://doi.org/10.1016/j.scitotenv.2020.143512 doi: 10.1016/j.scitotenv.2020.143512
[14]	Documentation for the TIMES Model Part Ⅳ, Energy Technology Systems Analysis Programme, 2016. Available from: https://iea-etsap.org/docs/Documentation_for_the_TIMES_Model-Part-IV_October-2016.pdf.
[15]	M. Guignard, S. Kim, Lagrangian decomposition: A model yielding stronger lagrangian relaxation bounds, Math. Program., 39 (1993), 215–228. https://doi.org/10.1007/BF02592954 doi: 10.1007/BF02592954
[16]	R. Horst, P. M. Pardalos, N. Van Thoai, Introduction to global optimization, Springer Science & Business Media, 2000.
[17]	C. S. Ioakimidis, K. N. Genikomsakis, Integration of seawater pumped-storage in the energy system of the Island of Sao Miguel (Azores), Sustainability, 10 (2018), 3438. https://doi.org/10.3390/su10103438 doi: 10.3390/su10103438
[18]	Y. Jia, R. Liu, Analysis of Beijing energy saving and emission reduction strategy based on times model, J. Basic Sci. Eng., 21 (2013), 857–865.
[19]	R. Kanala, E. Fragniere, Mixing behavioral and technological data in mathematical programming framework, In: Operations Research Proceedings 2012, Springer, 2014,163–168. https://doi.org/10.1007/978-3-319-00795-3_24
[20]	A. Kanudia, R. Loulou, Robust responses to climate change via stochastic MARKAL: The case of Quebec, Eur. J. Oper. Res., 106 (1998), 15–30. https://doi.org/10.1016/S0377-2217(98)00356-7 doi: 10.1016/S0377-2217(98)00356-7
[21]	K. Kim, V. M. Zavala, Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs, Math. Program. Comput., 10 (2018), 225–266. https://doi.org/10.1007/s12532-017-0128-z doi: 10.1007/s12532-017-0128-z
[22]	A. J. Kleywegt, A. Shapiro, T. Homem-de Mello, The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12 (2002), 479–502. https://doi.org/10.1137/S1052623499363220 doi: 10.1137/S1052623499363220
[23]	D. Kuhn, P. M. Esfahani, V. A. Nguyen, S. Shafieezadeh-Abadeh, Wasserstein distributionally robust optimization: Theory and applications in machine learning, Operations Research & Management Science in the Age of Analytics, 2019,130–166. https://doi.org/10.1287/educ.2019.0198
[24]	T. Larsson, C. O. Wene, Developing strategies for robust energy systems. Ⅰ: Methodology, Int. J. Energy Res., 17 (1993), 503–513. https://doi.org/10.1002/er.4440170606 doi: 10.1002/er.4440170606
[25]	P. Li, I. Keppo, N. Strachan, Incorporating homeowners' preferences of heating technologies in the UK TIMES model, Energy, 148 (2018), 716–727. https://doi.org/10.1016/j.energy.2018.01.150 doi: 10.1016/j.energy.2018.01.150
[26]	J. Liu, W. Chen, D. Liu, China's low carbon energy development strategy based on china times model system, J. Tsinghua Univ., 51 (2011), 525–529.
[27]	R. Loulou, M. Labriet, ETSAP-TIAM: The TIMES integrated assessment model Part Ⅰ: Model structure, Comput. Manag. Sci., 5 (2008), 7–40. https://doi.org/10.1007/s10287-007-0046-z doi: 10.1007/s10287-007-0046-z
[28]	Documentation for the TIMES Model Part Ⅰ, Energy Technology Systems Analysis Programme, 2016. Available from: https://iea-etsap.org/docs/Documentation_for_the_TIMES_Model-Part-I_July-2016.pdf.
[29]	Documentation for the TIMES Model Part Ⅱ, Energy Technology Systems Analysis Programme, 2016. Available from: https://iea-etsap.org/docs/Documentation_for_the_TIMES_Model-Part-II_July-2016.pdf.
[30]	M. J. Mayer, A. Szilágyi, G. Gróf, Environmental and economic multi-objective optimization of a household level hybrid renewable energy system by genetic algorithm, Appl. Energy, 269 (2020), 115058. https://doi.org/10.1016/j.apenergy.2020.115058 doi: 10.1016/j.apenergy.2020.115058
[31]	W. McDowall, B. S. Rodriguez, A. Usubiaga, J. A. Fernández, Is the optimal decarbonization pathway influenced by indirect emissions? Incorporating indirect life-cycle carbon dioxide emissions into a European TIMES model, J. Clean. Prod., 170 (2018), 260–268. https://doi.org/10.1016/j.jclepro.2017.09.132 doi: 10.1016/j.jclepro.2017.09.132
[32]	S. Pfenninger, A. Hawkes, J. Keirstead, Energy systems modeling for twenty-first century energy challenges, Renew. Sust. Energy Rev., 33 (2014), 74–86. https://doi.org/10.1016/j.rser.2014.02.003 doi: 10.1016/j.rser.2014.02.003
[33]	B. T. Polyak, Introduction to optimization, New York: Optimization Software Inc., Publications Division, 1987.
[34]	L. Qi, R. S. Womersley, An SQP algorithm for extended linear-quadratic problems in stochastic programming, Ann. Oper. Res., 56 (1995), 251–285. https://doi.org/10.1007/BF02031711 doi: 10.1007/BF02031711
[35]	W. Romeijnders, N. van der Laan, Pseudo-valid cutting planes for two-stage mixed-integer stochastic programs with right-hand-side uncertainty, Oper. Res., 68 (2020), 1199–1217. https://doi.org/10.1287/opre.2019.1905 doi: 10.1287/opre.2019.1905
[36]	A. M. Rush, M. J. Collins, A tutorial on dual decomposition and Lagrangian relaxation for inference in natural language processing, J. Artif. Intell. Res., 45 (2012), 305–362. https://doi.org/10.1613/jair.3680 doi: 10.1613/jair.3680
[37]	A. Schaefer, H. D. Jacoby, Technology detail in a multisector CGE model: Transport under climate policy, Energy Econ., 27 (2005), 1–24. https://doi.org/10.1016/j.eneco.2004.10.005 doi: 10.1016/j.eneco.2004.10.005
[38]	G. S. Seck, V. Krakowski, E. Assoumou, N. Maïzi, V. Mazauric, Embedding power system's reliability within a long-term Energy System Optimization Model: Linking high renewable energy integration and future grid stability for France by 2050, Appl. Energy, 257 (2020), 114037. https://doi.org/10.1016/j.apenergy.2019.114037 doi: 10.1016/j.apenergy.2019.114037
[39]	T. Schulze, Stochastic programming for hydro-thermal unit commitment, PhD's Thesis, The University of Edinburgh, 2015.
[40]	A. J. Seebregts, G. A. Goldstein, K. Smekens, Energy/environmental modeling with the MARKAL family of models, In: Operations Research Proceedings 2001, Springer, 2002, 75–82. https://doi.org/10.1007/978-3-642-50282-8_10
[41]	G. Tian, Z. Wu, Y. Hu, Calculation of optimal tax rate of water resources and analysis of social welfare based on CGE model: A case study in Hebei Province, China, Water Policy, 23 (2021), 96–113. https://doi.org/10.2166/wp.2020.118 doi: 10.2166/wp.2020.118
[42]	A Scottish TIMES Model: An Overview, The Scottish Government for the Environment, Climate Change and Land Reform Committee, 2016. Available from: https://archive2021.parliament.scot/S5_Environment/General%20Documents/20160922_Scottish_TIMES_model_-_an_overview.pdf.
[43]	UK TIMES Model Overview, UCL Energy Institute, 2014. Available from: https://www.ucl.ac.uk/drupal/site_energy-models/sites/energy-models/files/uk-times-overview.pdf.
[44]	Review of the Scottish TIMES Energy System Model, University College London, 2021. Available from: https://era.ed.ac.uk/handle/1842/37509.
[45]	R. M. Van Slyke, R. Wets, L-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math., 17 (1969), 638–663. https://doi.org/10.1137/0117061 doi: 10.1137/0117061
[46]	Y. Wang, Y. Wang, Y. Huang, F. Li, M. Zeng, J. Li, et al., Planning and operation method of the regional integrated energy system considering economy and environment, Energy, 171 (2019), 731–750. https://doi.org/10.1016/j.energy.2019.01.036 doi: 10.1016/j.energy.2019.01.036
[47]	Y. Zhang, M. Hong, J. Li, J. Ren, Y. Man, Energy system optimization model for tissue papermaking process, Comput. Chem. Eng., 146 (2021), 107220. https://doi.org/10.1016/j.compchemeng.2020.107220 doi: 10.1016/j.compchemeng.2020.107220
[48]	Z. X. Zhang, Can china afford to commit itself an emissions cap? An economic and political analysis, Energy Econ., 22 (2000), 587–614. https://doi.org/10.1016/S0140-9883(00)00048-7 doi: 10.1016/S0140-9883(00)00048-7

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)