IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v226y2013i2p341-353.html
   My bibliography  Save this article

Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model

Author

Listed:
  • Egging, Ruud

Abstract

This paper presents and implements a Benders Decomposition type of algorithm for large-scale, stochastic multi-period mixed complementarity problems. The algorithm is applied to various multi-stage natural gas market models accounting for market power exertion by traders. Due to the non-optimization nature of the natural gas market problem, a straightforward implementation of the traditional Benders Decomposition is not possible. The master and subproblems can be derived from the underlying optimization problems and transformed into complementarity problems. However, to complete the master problems optimality cuts are added using the variational inequality-based method developed in Gabriel and Fuller (2010). In this manner, an alternative derivation of Benders Decomposition for Stochastic MCP is presented, thereby making this approach more applicable to a broader audience. The algorithm can successfully solve problems with up to 256 scenarios and more than 600 thousand variables, and problems with over 117 thousand variables with more than two thousand first-stage capacity expansion variables. The algorithm is efficient for solving two-stage problems. The computational time reduction for other stochastic problems is considerable and would be even larger if a parallel implementation of the algorithm were used. The paper concludes with a discussion of infrastructure expansion results, illustrating the impact of hedging on investment timing and optimal capacity sizes.

Suggested Citation

  • Egging, Ruud, 2013. "Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model," European Journal of Operational Research, Elsevier, vol. 226(2), pages 341-353.
  • Handle: RePEc:eee:ejores:v:226:y:2013:i:2:p:341-353
    DOI: 10.1016/j.ejor.2012.11.024
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712008727
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fuller, J. David & Chung, William, 2008. "Benders decomposition for a class of variational inequalities," European Journal of Operational Research, Elsevier, vol. 185(1), pages 76-91, February.
    2. S. Gabriel & J. Fuller, 2010. "A Benders Decomposition Method for Solving Stochastic Complementarity Problems with an Application in Energy," Computational Economics, Springer;Society for Computational Economics, vol. 35(4), pages 301-329, April.
    3. Schütz, Peter & Tomasgard, Asgeir & Ahmed, Shabbir, 2009. "Supply chain design under uncertainty using sample average approximation and dual decomposition," European Journal of Operational Research, Elsevier, vol. 199(2), pages 409-419, December.
    4. Egging, Ruud & Gabriel, Steven A. & Holz, Franziska & Zhuang, Jifang, 2008. "A complementarity model for the European natural gas market," Energy Policy, Elsevier, vol. 36(7), pages 2385-2414, July.
    5. Lise, Wietze & Hobbs, Benjamin F. & van Oostvoorn, Frits, 2008. "Natural gas corridors between the EU and its main suppliers: Simulation results with the dynamic GASTALE model," Energy Policy, Elsevier, vol. 36(6), pages 1890-1906, June.
    6. Clemens Haftendorn & Franziska Holz, 2008. "Analysis of the World Market for Steam Coal Using a Complementarity Model," Discussion Papers of DIW Berlin 818, DIW Berlin, German Institute for Economic Research.
    7. Gabriel, Steven A. & Zhuang, Jifang & Egging, Ruud, 2009. "Solving stochastic complementarity problems in energy market modeling using scenario reduction," European Journal of Operational Research, Elsevier, vol. 197(3), pages 1028-1040, September.
    8. Jan Abrell & Hannes Weigt, 2012. "Combining Energy Networks," Networks and Spatial Economics, Springer, vol. 12(3), pages 377-401, September.
    9. Gabriel, S.A. & Rosendahl, K.E. & Egging, Ruud & Avetisyan, H.G. & Siddiqui, S., 2012. "Cartelization in gas markets: Studying the potential for a “Gas OPEC”," Energy Economics, Elsevier, vol. 34(1), pages 137-152.
    10. Zhuang, Jifang & Gabriel, Steven A., 2008. "A complementarity model for solving stochastic natural gas market equilibria," Energy Economics, Elsevier, vol. 30(1), pages 113-147, January.
    11. J. Fuller & William Chung, 2005. "Dantzig—Wolfe Decomposition of Variational Inequalities," Computational Economics, Springer;Society for Computational Economics, vol. 25(4), pages 303-326, June.
    12. Leuthold, Florian & Weigt, Hannes & von Hirschhausen, Christian, 2008. "Efficient pricing for European electricity networks - The theory of nodal pricing applied to feeding-in wind in Germany," Utilities Policy, Elsevier, vol. 16(4), pages 284-291, December.
    13. Lise, Wietze & Hobbs, Benjamin F., 2008. "Future evolution of the liberalised European gas market: Simulation results with a dynamic model," Energy, Elsevier, vol. 33(7), pages 989-1004.
    14. Daniel Huppmann & Franziska Holz, 2009. "A Model for the Global Crude Oil Market Using a Multi-Pool MCP Approach," Discussion Papers of DIW Berlin 869, DIW Berlin, German Institute for Economic Research.
    15. Canto, Salvador Perez, 2008. "Application of Benders' decomposition to power plant preventive maintenance scheduling," European Journal of Operational Research, Elsevier, vol. 184(2), pages 759-777, January.
    16. Maroeska G. Boots, Fieke A.M. Rijkers and Benjamin F. Hobbs, 2004. "Trading in the Downstream European Gas Market: A Successive Oligopoly Approach," The Energy Journal, International Association for Energy Economics, vol. 0(Number 3), pages 73-102.
    17. Cerisola, Santiago & Latorre, Jesus M. & Ramos, Andres, 2012. "Stochastic dual dynamic programming applied to nonconvex hydrothermal models," European Journal of Operational Research, Elsevier, vol. 218(3), pages 687-697.
    18. Ruud Egging, Franziska Holz, Christian von Hirschhausen and Steven A. Gabriel, 2009. "Representing GASPEC with the World Gas Model," The Energy Journal, International Association for Energy Economics, vol. 0(Special I), pages 97-118.
    19. Egging, Rudolf G. & Gabriel, Steven A., 2006. "Examining market power in the European natural gas market," Energy Policy, Elsevier, vol. 34(17), pages 2762-2778, November.
    20. Weigt, Hannes & Jeske, Till & Leuthold, Florian & von Hirschhausen, Christian, 2010. ""Take the long way down": Integration of large-scale North Sea wind using HVDC transmission," Energy Policy, Elsevier, vol. 38(7), pages 3164-3173, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Philipp M. Richter, 2015. "From Boom to Bust? A Critical Look at US Shale Gas Projections," Economics of Energy & Environmental Policy, International Association for Energy Economics, vol. 0(Number 1).
    2. Lynch, Muireann Á & Devine, Mel & Bertsch, Valentin, 2018. "The role of power-to-gas in the future energy system: how much is needed and who wants to invest?," Papers WP590, Economic and Social Research Institute (ESRI).
    3. Egging, Ruud & Pichler, Alois & Kalvø, Øyvind Iversen & Walle–Hansen, Thomas Meyer, 2017. "Risk aversion in imperfect natural gas markets," European Journal of Operational Research, Elsevier, vol. 259(1), pages 367-383.
    4. Richter, Philipp M. & Holz, Franziska, 2015. "All quiet on the eastern front? Disruption scenarios of Russian natural gas supply to Europe," Energy Policy, Elsevier, vol. 80(C), pages 177-189.
    5. repec:eee:eneeco:v:64:y:2017:i:c:p:520-529 is not listed on IDEAS
    6. Huppmann, Daniel & Egging, Ruud, 2014. "Market power, fuel substitution and infrastructure – A large-scale equilibrium model of global energy markets," Energy, Elsevier, vol. 75(C), pages 483-500.
    7. Daniel Huppmann, 2012. "Endogenous Investment Decisions in Natural Gas Equilibrium Models with Logarithmic Cost Functions," Discussion Papers of DIW Berlin 1253, DIW Berlin, German Institute for Economic Research.
    8. Feijoo, Felipe & Huppmann, Daniel & Sakiyama, Larissa & Siddiqui, Sauleh, 2016. "North American natural gas model: Impact of cross-border trade with Mexico," Energy, Elsevier, vol. 112(C), pages 1084-1095.
    9. Baltensperger, Tobias & Füchslin, Rudolf M. & Krütli, Pius & Lygeros, John, 2016. "Multiplicity of equilibria in conjectural variations models of natural gas markets," European Journal of Operational Research, Elsevier, vol. 252(2), pages 646-656.
    10. repec:eee:ejores:v:265:y:2018:i:2:p:437-447 is not listed on IDEAS
    11. Holz, Franziska & Brauers, Hanna & Richter, Philipp M. & Roobeek, Thorsten, 2017. "Shaking Dutch grounds won’t shatter the European gas market," Energy Economics, Elsevier, vol. 64(C), pages 520-529.
    12. repec:eee:ejores:v:267:y:2018:i:2:p:643-658 is not listed on IDEAS
    13. Bertsch, Valentin & Devine, Mel & Sweeney, Conor & Parnell, Andrew C., 2018. "Analysing long-term interactions between demand response and different electricity markets using a stochastic market equilibrium model," Papers WP585, Economic and Social Research Institute (ESRI).
    14. Egging, Ruud & Holz, Franziska, 2016. "Risks in global natural gas markets: Investment, hedging and trade," Energy Policy, Elsevier, vol. 94(C), pages 468-479.
    15. Rolf Golombek & Kjell Arne Brekke & Michal Kaut & Sverre A.C. Kittelsen & Stein W. Wallace, 2016. "Stochastic equilibrium modeling: The Impact of Uncertainty on the European Energy Market," EcoMod2016 9201, EcoMod.
    16. Franziska Holz & Philipp M. Richter & Ruud Egging, 2013. "The Role of Natural Gas in a Low-Carbon Europe: Infrastructure and Regional Supply Security in the Global Gas Model," Discussion Papers of DIW Berlin 1273, DIW Berlin, German Institute for Economic Research.
    17. Huppmann, Daniel, 2013. "Endogenous production capacity investment in natural gas market equilibrium models," European Journal of Operational Research, Elsevier, vol. 231(2), pages 503-506.
    18. repec:aen:journl:ej37-si3-holz is not listed on IDEAS
    19. Chyong, Chi Kong & Hobbs, Benjamin F., 2014. "Strategic Eurasian natural gas market model for energy security and policy analysis: Formulation and application to South Stream," Energy Economics, Elsevier, vol. 44(C), pages 198-211.
    20. repec:eee:energy:v:134:y:2017:i:c:p:984-990 is not listed on IDEAS

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:226:y:2013:i:2:p:341-353. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: http://www.elsevier.com/locate/eor .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.