IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v21y2024i1d10.1007_s10287-024-00509-y.html
   My bibliography  Save this article

Decomposition methods for multi-horizon stochastic programming

Author

Listed:
  • Hongyu Zhang

    (Norwegian University of Science and Technology)

  • Ignacio E. Grossmann

    (Carnegie Mellon University)

  • Asgeir Tomasgard

    (Norwegian University of Science and Technology)

Abstract

Multi-horizon stochastic programming includes short-term and long-term uncertainty in investment planning problems more efficiently than traditional multi-stage stochastic programming. In this paper, we exploit the block separable structure of multi-horizon stochastic linear programming, and establish that it can be decomposed by Benders decomposition and Lagrangean decomposition. In addition, we propose parallel Lagrangean decomposition with primal reduction that, (1) solves the scenario subproblems in parallel, (2) reduces the primal problem by keeping one copy for each scenario group at each stage, and (3) solves the reduced primal problem in parallel. We apply the parallel Lagrangean decomposition with primal reduction, Lagrangean decomposition and Benders decomposition to solve a stochastic energy system investment planning problem. The computational results show that: (a) the Lagrangean type decomposition algorithms have better convergence at the first iterations to Benders decomposition, and (b) parallel Lagrangean decomposition with primal reduction is very efficient for solving multi-horizon stochastic programming problems. Based on the computational results, the choice of algorithms for multi-horizon stochastic programming is discussed.

Suggested Citation

  • Hongyu Zhang & Ignacio E. Grossmann & Asgeir Tomasgard, 2024. "Decomposition methods for multi-horizon stochastic programming," Computational Management Science, Springer, vol. 21(1), pages 1-24, June.
    • Handle: RePEc:spr:comgts:v:21:y:2024:i:1:d:10.1007_s10287-024-00509-y
    DOI: 10.1007/s10287-024-00509-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10287-024-00509-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10287-024-00509-y?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
    ---><---

    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. Laureano F. Escudero & Juan F. Monge, 2018. "On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management," Computational Management Science, Springer, vol. 15(3), pages 479-500, October.
    2. Michal Kaut & Kjetil Midthun & Adrian Werner & Asgeir Tomasgard & Lars Hellemo & Marte Fodstad, 2014. "Multi-horizon stochastic programming," Computational Management Science, Springer, vol. 11(1), pages 179-193, January.
    3. John R. Birge, 1985. "Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs," Operations Research, INFORMS, vol. 33(5), pages 989-1007, October.
    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. Castro, Jordi & Escudero, Laureano F. & Monge, Juan F., 2023. "On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach," European Journal of Operational Research, Elsevier, vol. 310(1), pages 268-285.
    2. Escudero, Laureano F. & Monge, Juan F. & Rodríguez-Chía, Antonio M., 2020. "On pricing-based equilibrium for network expansion planning. A multi-period bilevel approach under uncertainty," European Journal of Operational Research, Elsevier, vol. 287(1), pages 262-279.
    3. Giovanni Pantuso & Trine K. Boomsma, 2020. "On the number of stages in multistage stochastic programs," Annals of Operations Research, Springer, vol. 292(2), pages 581-603, September.
    4. Domínguez, Ruth & Vitali, Sebastiano & Carrión, Miguel & Moriggia, Vittorio, 2021. "Analysing decarbonizing strategies in the European power system applying stochastic dominance constraints," Energy Economics, Elsevier, vol. 101(C).
    5. Laureano F. Escudero & Juan F. Monge, 2021. "On Multistage Multiscale Stochastic Capacitated Multiple Allocation Hub Network Expansion Planning," Mathematics, MDPI, vol. 9(24), pages 1-39, December.
    6. Sandeep Rath & Kumar Rajaram, 2022. "Staff Planning for Hospitals with Implicit Cost Estimation and Stochastic Optimization," Production and Operations Management, Production and Operations Management Society, vol. 31(3), pages 1271-1289, March.
    7. Ketabchi, Saeed & Behboodi-Kahoo, Malihe, 2015. "Augmented Lagrangian method within L-shaped method for stochastic linear programs," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 12-20.
    8. V.I. Norkin & G.C. Pflug & A. Ruszczynski, 1996. "A Branch and Bound Method for Stochastic Global Optimization," Working Papers wp96065, International Institute for Applied Systems Analysis.
    9. Gyana R. Parija & Shabbir Ahmed & Alan J. King, 2004. "On Bridging the Gap Between Stochastic Integer Programming and MIP Solver Technologies," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 73-83, February.
    10. Kai Huang & Shabbir Ahmed, 2009. "The Value of Multistage Stochastic Programming in Capacity Planning Under Uncertainty," Operations Research, INFORMS, vol. 57(4), pages 893-904, August.
    11. Ringkjøb, Hans-Kristian & Haugan, Peter M. & Nybø, Astrid, 2020. "Transitioning remote Arctic settlements to renewable energy systems – A modelling study of Longyearbyen, Svalbard," Applied Energy, Elsevier, vol. 258(C).
    12. Peter Kall & János Mayer, 2006. "Some insights into the solution algorithms for SLP problems," Annals of Operations Research, Springer, vol. 142(1), pages 147-164, February.
    13. Diana Barro & Elio Canestrelli, 2011. "Combining stochastic programming and optimal control to solve multistage stochastic optimization problems," Working Papers 2011_24, Department of Economics, University of Venice "Ca' Foscari", revised 2011.
    14. Maqsood, Imran & Huang, Guo H. & Scott Yeomans, Julian, 2005. "An interval-parameter fuzzy two-stage stochastic program for water resources management under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 208-225, November.
    15. Li, Y.P. & Huang, G.H. & Zhang, N. & Nie, S.L., 2011. "An inexact-stochastic with recourse model for developing regional economic-ecological sustainability under uncertainty," Ecological Modelling, Elsevier, vol. 222(2), pages 370-379.
    16. Julia Higle & Suvrajeet Sen, 2006. "Multistage stochastic convex programs: Duality and its implications," Annals of Operations Research, Springer, vol. 142(1), pages 129-146, February.
    17. Jacek Gondzio & Roy Kouwenberg, 2001. "High-Performance Computing for Asset-Liability Management," Operations Research, INFORMS, vol. 49(6), pages 879-891, December.
    18. Li, Y.P. & Huang, G.H. & Nie, S.L. & Chen, X., 2011. "A robust modeling approach for regional water management under multiple uncertainties," Agricultural Water Management, Elsevier, vol. 98(10), pages 1577-1588, August.
    19. F. Wu & H. Li & L. Chu & D. Sculli & K. Gao, 2009. "An approach to the valuation and decision of ERP investment projects based on real options," Annals of Operations Research, Springer, vol. 168(1), pages 181-203, April.
    20. Park, Jangho & Bayraksan, Güzin, 2023. "A multistage distributionally robust optimization approach to water allocation under climate uncertainty," European Journal of Operational Research, Elsevier, vol. 306(2), pages 849-871.

    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:spr:comgts:v:21:y:2024:i:1:d:10.1007_s10287-024-00509-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.