IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i1p34-50.html
   My bibliography  Save this article

High-Performance Prototyping of Decomposition Methods in GAMS

Author

Listed:
  • Timo Lohmann

    (Uniper Global Commodities SE, 40221 Düsseldorf, Germany)

  • Michael R. Bussieck

    (GAMS Development Corp., Fairfax, Virginia 22031)

  • Lutz Westermann

    (GAMS Software GmbH, 38102 Braunschweig, Germany)

  • Steffen Rebennack

    (Karlsruhe Institute of Technology, Institute of Operations Research, 76131 Karlsruhe, Germany)

Abstract

Prototyping algorithms in algebraic modeling languages has a long tradition. Despite the convenient prototyping platform that modeling languages offer, they are typically seen as rather inefficient with regard to repeatedly solving mathematical programming problems, a concept on which many algorithms are based. The most prominent examples of such algorithms are decomposition methods, such as the Benders decomposition, column generation, and the Dantzig–Wolfe decomposition. In this work, we discuss the underlying reasons for repeated solve deficiency with regard to speed in detail and provide an insider’s look into the algebraic modeling language GAMS. Further, we present recently added features in GAMS that mitigate some of the efficiency drawbacks inherent to the way modeling languages represent model data and ultimately solve a model. In particular, we demonstrate the grid-enabled gather-update-solve-scatter facility and the GAMS object-oriented application programming interface on a large-scale case study that involves a Benders decomposition–type algorithm for a power-expansion planning problem.

Suggested Citation

  • Timo Lohmann & Michael R. Bussieck & Lutz Westermann & Steffen Rebennack, 2021. "High-Performance Prototyping of Decomposition Methods in GAMS," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 34-50, January.
    • Handle: RePEc:inm:orijoc:v:33:y:2021:i:1:p:34-50
    DOI: 10.1287/ijoc.2019.0905
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2019.0905
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2019.0905?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Stephen Frank & Steffen Rebennack, 2016. "An introduction to optimal power flow: Theory, formulation, and examples," IISE Transactions, Taylor & Francis Journals, vol. 48(12), pages 1172-1197, December.
    2. P. Massé & R. Gibrat, 1957. "Application of Linear Programming to Investments in the Electric Power Industry," Management Science, INFORMS, vol. 3(2), pages 149-166, January.
    3. Jeremy A. Bloom & Michael Caramanis & Leonid Charny, 1984. "Long-Range Generation Planning Using Generalized Benders' Decomposition: Implementation and Experience," Operations Research, INFORMS, vol. 32(2), pages 290-313, April.
    4. Bushnell, James, 2010. "Building Blocks: Investment in Renewable and Non-Renewable Technologies," Staff General Research Papers Archive 31546, Iowa State University, Department of Economics.
    5. Fell, Harrison & Linn, Joshua, 2013. "Renewable electricity policies, heterogeneity, and cost effectiveness," Journal of Environmental Economics and Management, Elsevier, vol. 66(3), pages 688-707.
    6. Michael R. Bussieck & Michael C. Ferris & Alexander Meeraus, 2009. "Grid-Enabled Optimization with GAMS," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 349-362, August.
    7. Steeger, Gregory & Rebennack, Steffen, 2017. "Dynamic convexification within nested Benders decomposition using Lagrangian relaxation: An application to the strategic bidding problem," European Journal of Operational Research, Elsevier, vol. 257(2), pages 669-686.
    8. Timo Lohmann & Steffen Rebennack, 2017. "Tailored Benders Decomposition for a Long-Term Power Expansion Model with Short-Term Demand Response," Management Science, INFORMS, vol. 63(6), pages 2027-2048, June.
    9. Severin Borenstein, 2005. "The Long-Run Efficiency of Real-Time Electricity Pricing," The Energy Journal, International Association for Energy Economics, vol. 0(Number 3), pages 93-116.
    10. Lohmann, Timo & Hering, Amanda S. & Rebennack, Steffen, 2016. "Spatio-temporal hydro forecasting of multireservoir inflows for hydro-thermal scheduling," European Journal of Operational Research, Elsevier, vol. 255(1), pages 243-258.
    11. Jeremy A. Bloom, 1983. "Solving an Electricity Generating Capacity Expansion Planning Problem by Generalized Benders' Decomposition," Operations Research, INFORMS, vol. 31(1), pages 84-100, February.
    12. Frederic H. Murphy & Yves Smeers, 2005. "Generation Capacity Expansion in Imperfectly Competitive Restructured Electricity Markets," Operations Research, INFORMS, vol. 53(4), pages 646-661, August.
    13. Dennis Anderson, 1972. "Models for Determining Least-Cost Investments in Electricity Supply," Bell Journal of Economics, The RAND Corporation, vol. 3(1), pages 267-299, Spring.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Timo Lohmann & Steffen Rebennack, 2017. "Tailored Benders Decomposition for a Long-Term Power Expansion Model with Short-Term Demand Response," Management Science, INFORMS, vol. 63(6), pages 2027-2048, June.
    2. De Jonghe, C. & Hobbs, B. F. & Belmans, R., 2011. "Integrating short-term demand response into long-term investment planning," Cambridge Working Papers in Economics 1132, Faculty of Economics, University of Cambridge.
    3. Aliakbari Sani, Sajad & Bahn, Olivier & Delage, Erick, 2022. "Affine decision rule approximation to address demand response uncertainty in smart Grids’ capacity planning," European Journal of Operational Research, Elsevier, vol. 303(1), pages 438-455.
    4. Gacitua, L. & Gallegos, P. & Henriquez-Auba, R. & Lorca, Á. & Negrete-Pincetic, M. & Olivares, D. & Valenzuela, A. & Wenzel, G., 2018. "A comprehensive review on expansion planning: Models and tools for energy policy analysis," Renewable and Sustainable Energy Reviews, Elsevier, vol. 98(C), pages 346-360.
    5. Munoz, F.D. & Hobbs, B.F. & Watson, J.-P., 2016. "New bounding and decomposition approaches for MILP investment problems: Multi-area transmission and generation planning under policy constraints," European Journal of Operational Research, Elsevier, vol. 248(3), pages 888-898.
    6. Sajad Aliakbari Sani & Olivier Bahn & Erick Delage & Rinel Foguen Tchuendom, 2022. "Robust Integration of Electric Vehicles Charging Load in Smart Grid’s Capacity Expansion Planning," Dynamic Games and Applications, Springer, vol. 12(3), pages 1010-1041, September.
    7. Christian Gambardella & Michael Pahle & Wolf-Peter Schill, 2016. "Do Benefits from Dynamic Tariffing Rise? Welfare Effects of Real-Time Pricing under Carbon-Tax-Induced Variable Renewable Energy Supply," Discussion Papers of DIW Berlin 1621, DIW Berlin, German Institute for Economic Research.
    8. Merrick, James H. & Bistline, John E.T. & Blanford, Geoffrey J., 2024. "On representation of energy storage in electricity planning models," Energy Economics, Elsevier, vol. 136(C).
    9. Pineau, Pierre-Olivier & Rasata, Hasina & Zaccour, Georges, 2011. "Impact of some parameters on investments in oligopolistic electricity markets," European Journal of Operational Research, Elsevier, vol. 213(1), pages 180-195, August.
    10. Bajo-Buenestado, Raúl, 2017. "Welfare implications of capacity payments in a price-capped electricity sector: A case study of the Texas market (ERCOT)," Energy Economics, Elsevier, vol. 64(C), pages 272-285.
    11. Cullen, Joseph A. & Reynolds, Stanley S., 2023. "Market dynamics and investment in the electricity sector," International Journal of Industrial Organization, Elsevier, vol. 89(C).
    12. Bunn, Derek W. & Oliveira, Fernando S., 2016. "Dynamic capacity planning using strategic slack valuation," European Journal of Operational Research, Elsevier, vol. 253(1), pages 40-50.
    13. Zhong, Zhiming & Fan, Neng & Wu, Lei, 2023. "A hybrid robust-stochastic optimization approach for day-ahead scheduling of cascaded hydroelectric system in restructured electricity market," European Journal of Operational Research, Elsevier, vol. 306(2), pages 909-926.
    14. Charles Gauvin & Erick Delage & Michel Gendreau, 2018. "A successive linear programming algorithm with non-linear time series for the reservoir management problem," Computational Management Science, Springer, vol. 15(1), pages 55-86, January.
    15. Wichsinee Wibulpolprasert, 2016. "Optimal Environmental Policies And Renewable Energy Investment: Evidence From The Texas Electricity Market," Climate Change Economics (CCE), World Scientific Publishing Co. Pte. Ltd., vol. 7(04), pages 1-41, November.
    16. López-Ramos, Francisco & Nasini, Stefano & Sayed, Mohamed H., 2020. "An integrated planning model in centralized power systems," European Journal of Operational Research, Elsevier, vol. 287(1), pages 361-377.
    17. Francisco Munoz & Jean-Paul Watson, 2015. "A scalable solution framework for stochastic transmission and generation planning problems," Computational Management Science, Springer, vol. 12(4), pages 491-518, October.
    18. Zong Woo Geem & Jin-Hong Kim, 2016. "Optimal Energy Mix with Renewable Portfolio Standards in Korea," Sustainability, MDPI, vol. 8(5), pages 1-14, May.
    19. Mar Reguant, 2018. "The Efficiency and Sectoral Distributional Implications of Large-Scale Renewable Policies," NBER Working Papers 24398, National Bureau of Economic Research, Inc.
    20. Gal, Nurit & Milstein, Irena & Tishler, Asher & Woo, C.K., 2019. "Investment in electricity capacity under fuel cost uncertainty: Dual-fuel and a mix of single-fuel technologies," Energy Policy, Elsevier, vol. 126(C), pages 518-532.

    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:inm:orijoc:v:33:y:2021:i:1:p:34-50. See general information about how to correct material in RePEc.

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

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.