IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v284y2020i2d10.1007_s10479-018-2880-5.html
   My bibliography  Save this article

An accelerated L-shaped method for solving two-stage stochastic programs in disaster management

Author

Listed:
  • Emilia Grass

    (Hamburg University of Technology)

  • Kathrin Fischer

    (Hamburg University of Technology)

  • Antonia Rams

    (Hamburg University of Technology)

Abstract

Mitigating the disastrous effects of natural disasters by performing preparation activities is one of the main purposes of relief organizations. However, the high degree of uncertainty associated with disasters impedes the work of aid agencies considerably. In this regard, two-stage stochastic programs are often used in the relevant literature to support decision making in these situations. An accelerated L-shaped method is proposed in this work, which solves realistic large-scale two-stage stochastic problems within a reasonable time-frame, allowing relief organizations to react to short-term forecasts, as e.g. available in case of hurricanes or floods. In particular, computation times needed for solving the resulting sub-problems via a specialized interior-point method are significantly reduced by exploiting the specific structure of second-stage constraints. To show the superiority of this approach with respect to solution times, a realistic large-scale case study is developed for America’s hurricane-prone south-east coast. The accelerated L-shaped method outperforms the standard L-shaped method significantly whereas a commercial solver failed to solve the case study within an acceptable time-frame.

Suggested Citation

  • Emilia Grass & Kathrin Fischer & Antonia Rams, 2020. "An accelerated L-shaped method for solving two-stage stochastic programs in disaster management," Annals of Operations Research, Springer, vol. 284(2), pages 557-582, January.
    • Handle: RePEc:spr:annopr:v:284:y:2020:i:2:d:10.1007_s10479-018-2880-5
    DOI: 10.1007/s10479-018-2880-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-018-2880-5
    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/s10479-018-2880-5?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. Georgios Saharidis & Marianthi Ierapetritou, 2013. "Speed-up Benders decomposition using maximum density cut (MDC) generation," Annals of Operations Research, Springer, vol. 210(1), pages 101-123, November.
    2. Hanif Sherali & Brian Lunday, 2013. "On generating maximal nondominated Benders cuts," Annals of Operations Research, Springer, vol. 210(1), pages 57-72, November.
    3. 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.
    4. Joe Naoum-Sawaya & Samir Elhedhli, 2013. "An interior-point Benders based branch-and-cut algorithm for mixed integer programs," Annals of Operations Research, Springer, vol. 210(1), pages 33-55, November.
    5. Qipeng Zheng & Jianhui Wang & Panos Pardalos & Yongpei Guan, 2013. "A decomposition approach to the two-stage stochastic unit commitment problem," Annals of Operations Research, Springer, vol. 210(1), pages 387-410, November.
    6. Rawls, Carmen G. & Turnquist, Mark A., 2010. "Pre-positioning of emergency supplies for disaster response," Transportation Research Part B: Methodological, Elsevier, vol. 44(4), pages 521-534, May.
    7. Emmanuel Fragnière & Jacek Gondzio & Jean-Philippe Vial, 2000. "Building and Solving Large-Scale Stochastic Programs on an Affordable Distributed Computing System," Annals of Operations Research, Springer, vol. 99(1), pages 167-187, December.
    8. Urmila Diwekar, 2008. "Introduction to Applied Optimization," Springer Optimization and Its Applications, Springer, number 978-0-387-76635-5, June.
    9. repec:spr:pharme:v:21:y:2003:i:12:p:839-851 is not listed on IDEAS
    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. Sophie N. Parragh & Fabien Tricoire & Walter J. Gutjahr, 2022. "A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 419-459, June.
    2. Dukkanci, Okan & Koberstein, Achim & Kara, Bahar Y., 2023. "Drones for relief logistics under uncertainty after an earthquake," European Journal of Operational Research, Elsevier, vol. 310(1), pages 117-132.
    3. Liu, Tongxin & Shao, Jianfang & Wang, Xihui, 2022. "Funding allocations for disaster preparation considering catastrophe insurance," Socio-Economic Planning Sciences, Elsevier, vol. 84(C).

    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. N. Beheshti Asl & S. A. MirHassani, 2019. "Accelerating benders decomposition: multiple cuts via multiple solutions," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 806-826, April.
    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. 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.
    4. 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.
    5. Zhang, Yuwei & Li, Zhenping & Zhao, Yuwei, 2023. "Multi-mitigation strategies in medical supplies for epidemic outbreaks," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    6. René Brandenberg & Paul Stursberg, 2021. "Refined cut selection for benders decomposition: applied to network capacity expansion problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 94(3), pages 383-412, December.
    7. Guo, Penghui & Zhu, Jianjun, 2023. "Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut," European Journal of Operational Research, Elsevier, vol. 311(3), pages 942-970.
    8. 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.
    9. Elçi, Özgün & Noyan, Nilay, 2018. "A chance-constrained two-stage stochastic programming model for humanitarian relief network design," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 55-83.
    10. Simon Emde & Shohre Zehtabian & Yann Disser, 2023. "Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition," Annals of Operations Research, Springer, vol. 322(1), pages 467-496, March.
    11. Hooshmand, F. & Mirarabrazi, F. & MirHassani, S.A., 2020. "Efficient Benders decomposition for distance-based critical node detection problem," Omega, Elsevier, vol. 93(C).
    12. Nilay Noyan & Gökçe Kahvecioğlu, 2018. "Stochastic last mile relief network design with resource reallocation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 187-231, January.
    13. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    14. Zhouchun Huang & Qipeng P. Zheng & Andrew L. Liu, 2022. "A Nested Cross Decomposition Algorithm for Power System Capacity Expansion with Multiscale Uncertainties," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1919-1939, July.
    15. 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.
    16. Vedat Bayram & Hande Yaman, 2018. "Shelter Location and Evacuation Route Assignment Under Uncertainty: A Benders Decomposition Approach," Transportation Science, INFORMS, vol. 52(2), pages 416-436, March.
    17. Placido dos Santos, Felipe Silva & Oliveira, Fabricio, 2019. "An enhanced L-Shaped method for optimizing periodic-review inventory control problems modeled via two-stage stochastic programming," European Journal of Operational Research, Elsevier, vol. 275(2), pages 677-693.
    18. Zheng, Xiaojin & Yin, Meixia & Zhang, Yanxia, 2019. "Integrated optimization of location, inventory and routing in supply chain network design," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 1-20.
    19. Malihe Niksirat & Mohsen Saffarian & Javad Tayyebi & Adrian Marius Deaconu & Delia Elena Spridon, 2024. "Fuzzy Multi-Objective, Multi-Period Integrated Routing–Scheduling Problem to Distribute Relief to Disaster Areas: A Hybrid Ant Colony Optimization Approach," Mathematics, MDPI, vol. 12(18), pages 1-17, September.
    20. 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.

    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:annopr:v:284:y:2020:i:2:d:10.1007_s10479-018-2880-5. 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.