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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Warm-starting is to use the solution to the previous problem as a starting point for the next problem. Especially simplex algorithms benefit from such warm-start points and can find the next solution after only few iterations. However, developing efficient warm-start strategies for interior-point methods is an active research area nowadays, see e.g. Cay et al. (2017).
Note that it is very unlikely that a scenario will occur exactly as predefined. Moreover, penalty costs for unsatisfied demand are only fictitious and used to minimize unmet demand.
The reader is referred to Birge and Louveaux (2011) for a thorough description of two-stage stochastic programs in general.
Note that simplex multipliers are also known as shadow prices which are available, e.g. in the final tableau of the simplex algorithm (Diwekar 2008, p. 23). However, the dual sub-problem will be important for the primal–dual interior-point method described in the next section.
For two-stage stochastic models where no complete recourse is given, so-called feasibility cuts have to be included to the master problem in addition to the optimality cuts (Birge and Louveaux 2011, Ch 5).
The approach is presented for one sub-problem such that the subscript s is omitted for now.
See Ferris et al. (2007) for a general description of the Newton method for interior-point algorithms.
An approach for setting the step length \(\alpha \) can be found in Ferris et al. (2007).
In such cases the matrix \(W D^{-1} W^T\) is often dense leading to an increased effort when computing its inverse.
Distances are determined by the ArcGIS software.
The built-in function linprog uses a predictor-corrector primal–dual interior-point method by default.
Such termination criteria are common for interior-point methods (Wright 1997, p. 226).
By default, Gurobi solves the MIP root node via the dual simplex method and run the barrier and simplex method on multiple threads concurrently for LP problems (Gurobi Optimization 2017).
For comparison reasons Gurobi was terminated if the relative optimality gap fell below 0.009. However, the relative optimality gap jumped from 0.173 to 0.004 in the last iteration of Gurobi.
As mentioned above, column ’L-Shaped’ in Table 6 refers to the method where MATLAB’s linprog and ’Accelerated L-Shaped’ where SIPM is used for solving the sub-problems. Since computation times for solving the master problem in each iteration are independent of the sub-problems and insignificant in comparison to the solution times of the sub-problems, the overall time for the L-shaped method consists mainly of computation times for the sub-problems. Therefore, solution times given in Table 7 have a major influence on the overall solution times of the L-shaped method as given in Table 6.
References
Birge, J., & Louveaux, F. (2011). Introduction to stochastic programming. Berlin: Springer.
Castro, J. (2000). A specialized interior-point algorithm for multicommodity network flows. SIAM Journal on Optimization, 10(3), 852–877. https://doi.org/10.1137/S1052623498341879.
Castro, J., Nasini, S., & Saldanha-da Gama, F. (2016). A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method. Mathematical Programming,. https://doi.org/10.1007/s10107-016-1067-6.
Cay, S. B, Pólik, I., & Terlaky, T. (2017). Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames. Technical report, ISE technical report 17T-006, Lehigh University, 2017. http://www.optimization-online.org/DB_HTML/2017/05/5998.html.
De Silva, A., & Abramson, D. (1998). A parallel interior point method and its application to facility location problems. Computational Optimization and Applications, 9(3), 249–273.
Diwekar, U. (2008). Introduction to applied optimization. Springer. http://www.ebook.de/de/product/7522360/urmila_diwekar_introduction_to_applied_optimization.html.
Ferris, M., Mangasarian, O., & Wright, S. (2007). Linear programming with MATLAB. Society for Industrial and Applied Mathematics,. https://doi.org/10.1137/1.9780898718775.
Fragnière, E., Gondzio, J., & Vial, J. P. (2000). Building and solving large-scale stochastic programs on an affordable distributed computing system. Annals of Operations Research, 99(1), 167–187. https://doi.org/10.1023/A:1019245101545.
Golub, G. H., & Van Loan, C. F. (2013). Matrix computations (4th ed.). Baltimore: John Hopkins.
Gondzio, J., & Sarkissian, R. (2003). Parallel interior-point solver for structured linear programs. Mathematical Programming, 96(3), 561–584.
Grass, E., & Fischer, K. (2016). Two-stage stochastic programming in disaster management: A literature survey. Surveys in Operations Research and Management Science, 21(2), 85–100. https://doi.org/10.1016/j.sorms.2016.11.002.
Gurobi Optimization. (2017). Parameter documentation. http://www.gurobi.com/documentation/7.5/refman/method.html#parameter:Method. Accessed December 05, 2017.
Hu, Y., Maguire, K., & Blake, R. (2000). A multilevel unsymmetric matrix ordering algorithm for parallel process simulation. Computers & Chemical Engineering, 23(11), 1631–1647. https://doi.org/10.1016/S0098-1354(99)00314-2.
IFRC. (2016). International federation of red cross and red crescent societies—Items catalogue. http://procurement.ifrc.org/catalogue/detail.aspx. Accessed January 01, 2017.
MSF. (2016). Aerzte ohne Grenzen e.V.-Private Communication.
Naoum-Sawaya, J., & Elhedhli, S. (2013). An interior-point Benders based branch-and-cut algorithm for mixed integer programs. Annals of Operations Research, 210(1), 33–55. https://doi.org/10.1007/s10479-010-0806-y.
Nielsen, S. S., & Zenios, S. A. (1997). Scalable parallel Benders decomposition for stochastic linear programming. Parallel Computing, 23(8), 1069–1088. https://doi.org/10.1016/S0167-8191(97)00044-6.
NOAA/AOML. (2016). National oceanic and atmospheric administration/Atlantic oceanographic and meteorological laboratory. http://www.aoml.noaa.gov/hrd/tcfaq/D5.html. Accessed August 18, 2017.
Pay, B. S., & Song, Y. (2017). Partition-based decomposition algorithms for two-stage stochastic integer programs with continuous recourse. Annals of Operations Research,. https://doi.org/10.1007/s10479-017-2689-7.
Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801–817. https://doi.org/10.1016/j.ejor.2016.12.005.
Rawls, C. G., & Turnquist, M. A. (2010). Pre-positioning of emergency supplies for disaster response. Transportation Research Part B: Methodological, 44(4), 521–534. https://doi.org/10.1016/j.trb.2009.08.003.
Saharidis, G. K. D., & Ierapetritou, M. G. (2013). Speed-up benders decomposition using maximum density cut (mdc) generation. Annals of Operations Research, 210(1), 101–123. https://doi.org/10.1007/s10479-012-1237-8.
SCEMD. (2007). South Carolina emergency management division-South Carolina logistical operations plan: Appendix 7. http://dc.statelibrary.sc.gov/handle/10827/20614. Accessed August 18, 2017.
Sherali, H. D., & Lunday, B. J. (2013). On generating maximal nondominated benders cuts. Annals of Operations Research, 210(1), 57–72. https://doi.org/10.1007/s10479-011-0883-6.
Slyke, R. M. V., & Wets, R. (1969). L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics, 17(4), 638–663. https://doi.org/10.1137/0117061.
Turkeš, R., Cuervo, D. P., & Sörensen, K. (2017). Pre-positioning of emergency supplies: Does putting a price on human life help to save lives? Annals of Operations Research,. https://doi.org/10.1007/s10479-017-2702-1.
URI/GSO. (2016). University of Rhode Island and Graduate School of Oceanography-Hurricanes: Science and Society. http://www.hurricanescience.org/science/science/hurricanestructure/. Accessed August 18, 2017.
Wright, S. J. (1997). Primal–dual interior-point methods. Philadelphia: SIAM. https://doi.org/10.1137/1.9781611971453.bm.
Zheng, Q. P., Wang, J., Pardalos, P. M., & Guan, Y. (2013). A decomposition approach to the two-stage stochastic unit commitment problem. Annals of Operations Research, 210(1), 387–410. https://doi.org/10.1007/s10479-012-1092-7.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Grass, E., Fischer, K. & Rams, A. An accelerated L-shaped method for solving two-stage stochastic programs in disaster management. Ann Oper Res 284, 557–582 (2020). https://doi.org/10.1007/s10479-018-2880-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-018-2880-5