IDEAS home Printed from https://ideas.repec.org/a/spr/topjnl/v29y2021i3d10.1007_s11750-021-00593-2.html
   My bibliography  Save this article

A column-and-constraint generation algorithm for two-stage stochastic programming problems

Author

Listed:
  • Denise D. Tönissen

    (Vrije Universiteit Amsterdam)

  • Joachim J. Arts

    (University of Luxembourg)

  • Zuo-Jun Max Shen

    (University of California)

Abstract

This paper presents a column-and-constraint generation algorithm for two-stage stochastic programming problems. A distinctive feature of the algorithm is that it does not assume fixed recourse and as a consequence the values and dimensions of the recourse matrix can be uncertain. The proposed algorithm contains multi-cut (partial) Benders decomposition and the deterministic equivalent model as special cases and can be used to trade-off computational speed and memory requirements. The algorithm outperforms multi-cut (partial) Benders decomposition in computational time and the deterministic equivalent model in memory requirements for a maintenance location routing problem. In addition, for instances with a large number of scenarios, the algorithm outperforms the deterministic equivalent model in both computational time and memory requirements. Furthermore, we present an adaptive relative tolerance for instances for which the solution time of the master problem is the bottleneck and the slave problems can be solved relatively efficiently. The adaptive relative tolerance is large in early iterations and converges to zero for the final iteration(s) of the algorithm. The combination of this relative adaptive tolerance with the proposed algorithm decreases the computational time of our instances even further.

Suggested Citation

  • Denise D. Tönissen & Joachim J. Arts & Zuo-Jun Max Shen, 2021. "A column-and-constraint generation algorithm for two-stage stochastic programming problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(3), pages 781-798, October.
    • Handle: RePEc:spr:topjnl:v:29:y:2021:i:3:d:10.1007_s11750-021-00593-2
    DOI: 10.1007/s11750-021-00593-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11750-021-00593-2
    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/s11750-021-00593-2?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. An, Yu & Zeng, Bo & Zhang, Yu & Zhao, Long, 2014. "Reliable p-median facility location problem: two-stage robust models and algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 64(C), pages 54-72.
    2. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    3. Birge, John R. & Louveaux, Francois V., 1988. "A multicut algorithm for two-stage stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 34(3), pages 384-392, March.
    4. Fengqi You & Ignacio Grossmann, 2013. "Multicut Benders decomposition algorithm for process supply chain planning under uncertainty," Annals of Operations Research, Springer, vol. 210(1), pages 191-211, November.
    5. Denise D. Tönissen & Joachim J. Arts & Zuo-Jun (Max) Shen, 2019. "Maintenance Location Routing for Rolling Stock Under Line and Fleet Planning Uncertainty," Transportation Science, INFORMS, vol. 53(5), pages 1252-1270, September.
    6. A. M. Geoffrion & G. W. Graves, 1974. "Multicommodity Distribution System Design by Benders Decomposition," Management Science, INFORMS, vol. 20(5), pages 822-844, January.
    7. Contreras, Ivan & Cordeau, Jean-François & Laporte, Gilbert, 2011. "Stochastic uncapacitated hub location," European Journal of Operational Research, Elsevier, vol. 212(3), pages 518-528, August.
    8. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2015. "Benders Decomposition for Production Routing Under Demand Uncertainty," Operations Research, INFORMS, vol. 63(4), pages 851-867, 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. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    2. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    3. Gruson, Matthieu & Cordeau, Jean-François & Jans, Raf, 2021. "Benders decomposition for a stochastic three-level lot sizing and replenishment problem with a distribution structure," European Journal of Operational Research, Elsevier, vol. 291(1), pages 206-217.
    4. Kiho Seo & Seulgi Joung & Chungmok Lee & Sungsoo Park, 2022. "A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2804-2827, September.
    5. de Sá, Elisangela Martins & de Camargo, Ricardo Saraiva & de Miranda, Gilberto, 2013. "An improved Benders decomposition algorithm for the tree of hubs location problem," European Journal of Operational Research, Elsevier, vol. 226(2), pages 185-202.
    6. Yin, Yunqiang & Luo, Zunhao & Wang, Dujuan & Cheng, T.C.E., 2023. "Wasserstein distance‐based distributionally robust parallel‐machine scheduling," Omega, Elsevier, vol. 120(C).
    7. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    8. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    9. Fragkogios, Antonios & Qiu, Yuzhuo & Saharidis, Georgios K.D. & Pardalos, Panos M., 2024. "An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 317(2), pages 500-514.
    10. Hermann, Alexander & Jensen, Tue Vissing & Østergaard, Jacob & Kazempour, Jalal, 2022. "A complementarity model for electric power transmission-distribution coordination under uncertainty," European Journal of Operational Research, Elsevier, vol. 299(1), pages 313-329.
    11. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    12. An, Yu & Zhang, Yu & Zeng, Bo, 2015. "The reliable hub-and-spoke design problem: Models and algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 103-122.
    13. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    14. Hassan Zohali & Bahman Naderi & Vahid Roshanaei, 2022. "Solving the Type-2 Assembly Line Balancing with Setups Using Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 315-332, January.
    15. Dursun, Pınar & Taşkın, Z. Caner & Altınel, İ. Kuban, 2019. "The determination of optimal treatment plans for Volumetric Modulated Arc Therapy (VMAT)," European Journal of Operational Research, Elsevier, vol. 272(1), pages 372-388.
    16. Gopalakrishnan Easwaran & Halit Üster, 2009. "Tabu Search and Benders Decomposition Approaches for a Capacitated Closed-Loop Supply Chain Network Design Problem," Transportation Science, INFORMS, vol. 43(3), pages 301-320, August.
    17. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    18. Nader Ghaffarinasab & Bahar Y. Kara, 2019. "Benders Decomposition Algorithms for Two Variants of the Single Allocation Hub Location Problem," Networks and Spatial Economics, Springer, vol. 19(1), pages 83-108, March.
    19. Bernardes Real, Luiza & O'Kelly, Morton & de Miranda, Gilberto & Saraiva de Camargo, Ricardo, 2018. "The gateway hub location problem," Journal of Air Transport Management, Elsevier, vol. 73(C), pages 95-112.
    20. Nathan Sudermann‐Merx & Steffen Rebennack & Christian Timpe, 2021. "Crossing Minimal Edge‐Constrained Layout Planning using Benders Decomposition," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3429-3447, October.

    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:topjnl:v:29:y:2021:i:3:d:10.1007_s11750-021-00593-2. 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.