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

Journal
Annals of operations research  
Volume
284
Issue
2
Start Page
557
End Page
582
Citation
Annals of Operations Research 2 (284): 557-582 (2020)
Publisher DOI
10.1007/s10479-018-2880-5
Scopus ID
2-s2.0-85046905198
Publisher
Springer Science + Business Media B.V.
© 2018, Springer Science+Business Media, LLC, part of Springer Nature. 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.
Subjects
Disaster management
Interior-point methods
L-shaped method
Stochastic Benders decomposition
Two-stage stochastic programming
DDC Class
004: Informatik
330: Wirtschaft