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. Bushnell, James, 2010. "Building blocks: investment in renewable and non-renewable technologies," ISU General Staff Papers 201005250700001113, Iowa State University, Department of Economics.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    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. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    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. 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.
    5. 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.
    6. 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.
    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. Pahle, Michael & Schill, Wolf-Peter & Gambardella, Christian & Tietjen, Oliver, 2016. "Renewable Energy Support, Negative Prices, and Real-time Pricing," EconStor Open Access Articles and Book Chapters, ZBW - Leibniz Information Centre for Economics, vol. 37, pages 147-169.
    11. 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.
    12. Cullen, Joseph A. & Reynolds, Stanley S., 2023. "Market dynamics and investment in the electricity sector," International Journal of Industrial Organization, Elsevier, vol. 89(C).
    13. 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.
    14. Mendes, Carla & Soares, Isabel, 2014. "Renewable energies impacting the optimal generation mix: The case of the Iberian Electricity Market," Energy, Elsevier, vol. 69(C), pages 23-33.
    15. Andreas Ehrenmann & Yves Smeers, 2011. "Generation Capacity Expansion in a Risky Environment: A Stochastic Equilibrium Analysis," Operations Research, INFORMS, vol. 59(6), pages 1332-1346, December.
    16. Milstein, Irena & Tishler, Asher, 2015. "Can price volatility enhance market power? The case of renewable technologies in competitive electricity markets," Resource and Energy Economics, Elsevier, vol. 41(C), pages 70-90.
    17. Li, Can & Conejo, Antonio J. & Liu, Peng & Omell, Benjamin P. & Siirola, John D. & Grossmann, Ignacio E., 2022. "Mixed-integer linear programming models and algorithms for generation and transmission expansion planning of power systems," European Journal of Operational Research, Elsevier, vol. 297(3), pages 1071-1082.
    18. 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.
    19. 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.
    20. Jikai Zou & Shabbir Ahmed & Xu Andy Sun, 2018. "Partially Adaptive Stochastic Optimization for Electric Power Generation Expansion Planning," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 388-401, May.

    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.