Application of decomposition techniques in a wildfire suppression optimization model
Tóm tắt
Resource assignment and scheduling models provides an automatic and fast decision support system for wildfire suppression logistics. However, this process generates challenging optimization problems in many real-world cases, and the computational time becomes a critical issue, especially in realistic-size instances. Thus, to overcome that limitation, this work studies and applies a set of decomposition techniques such as augmented Lagrangian, branch and price, and Benders decomposition’s to a wildfire suppression model. Moreover, a reformulation strategy, inspired by Benders’ decomposition, is also introduced and demonstrated. Finally, a numerical study comparing the behavior of the proposals using different problem sizes is conducted.
Tài liệu tham khảo
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46:316–329
Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4:238–252
Caunhye AM, Nie X, Pokharel S (2012) Optimization models in emergency logistics: a literature review. Socioecon Plann Sci 46:4–13
Commission European (2020) Forest fires in Europe, Middle East and North Africa 2019. Technical report, JRC technical reports
Conejo A, Castillo E, Mínguez R, García-Bertrand R (2006) Decomposition techniques in mathematical programming: engineering and science applications. Springer
Cordeau JF, Stojković G, Soumis F, Desrosiers J (2001) Benders decomposition for simultaneous aircraft routing and crew scheduling. Transp Sci INFORMS 35:375–388
Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91:201–213
Donovan GH, Rideout DB (2003) An integer programming model to optimize resource allocation for wildfire containment. For Sci 49:331–335
Finney MA (1998) FARSITE: fire area simulator—model development and evaluation, vol 3. United States Department of Agriculture, Forest Service, Rocky Mountain Research Station
Fisher ML (2004) The Lagrangian relaxation method for solving integer programming problems. Manag Sci 50:1861–1871
Gleixner A, Bastubbe M, Eifler L, Gally T, Gamrath G, Gottwald RL, Hendel G, Hojny C, Koch T, Lübbecke ME, Maher SJ, Miltenberger M, Müller B, Pfetsch ME, Puchert C, Rehfeldt D, Schlösser F, Schubert C, Serrano F, Shinano Y, Viernickel JM, Walter M, Wegscheider F, Witt JT, Witzig J (2018) The SCIP optimization suite 6.0. Technical report. Optimization online. http://www.optimization-online.org/DB_HTML/2018/07/6692.html
Gorte JK, Gorte RW (1979) Application of economic techniques to fire management—a status review and evaluation. Gen. Tech. Rep. INT-GTR-53. US Department of Agriculture, Forest Service, Intermountain Research Station, Ogden, vol 26, p 53
Gurobi Optimization L (2020) Gurobi optimizer reference manual. http://www.gurobi.com
Hamdi A, Mishra SK (2011) Decomposition methods based on augmented Lagrangians: a survey. In: Topics in nonconvex optimization. Springer, pp 175–203
Headley R (1916) Fire suppression, district 5. USDA-Forest Service, pp 1–57
Martell DL (2015) A review of recent forest and wildland fire management decision support systems research. Curr For Rep 1:128–137
Miller C, Ager AA (2013) A review of recent advances in risk analysis for wildfire management. Int J Wildland Fire 22:1–14
Minas JP, Hearne JW, Handmer JW (2012) A review of operations research methods applicable to wildfire management. Int J Wildland Fire 21:189–196
Ntaimo L, Arrubla JAG, Stripling C, Young J, Spencer T (2012) A stochastic programming standard response model for wildfire initial attack planning. Can J For Res 42:987–1001
Papadakos N (2009) Integrated airline scheduling. Comput Oper Res 36:176–195
Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The benders decomposition algorithm: a literature review. Eur J Oper Res 259:801–817. https://doi.org/10.1016/j.ejor.2016.12.005
Rios J, Ross K (2010) Massively parallel Dantzig–Wolfe decomposition applied to traffic flow scheduling. J Aerosp Comput Inf Commun 7:32–45
Rodríguez-Veiga J, Ginzo-Villamayor MJ, Casas-Méndez B (2018) An integer linear programming model to select and temporally allocate resources for fighting forest fires. Forests 9:583
Romanski J, Hentenryck PV (2016) Benders decomposition for large-scale prescriptive evacuations. In: AAAAI’16: Proceedings of the thirtieth AAAI conference on artificial intelligence, pp 3894–3900
Sethi S, Sorger G (1991) A theory of rolling horizon decision making. Ann Oper Res 29:387–415
Sparhawk WN (1925) The use of liability ratings in planning forest fire protection. National Emergency Training Center, Emmitsburg
Vanderbeck F, Savelsbergh MW (2006) A generic view of Dantzig–Wolfe decomposition in mixed integer programming. Oper Res Lett 34:296–306
Vanderbeck F, Wolsey LA (1996) An exact algorithm for IP column generation. Oper Res Lett 19:151–159
Wei Y, Rideout DB, Hall TB (2011) Toward efficient management of large fires: a mixed integer programming model and two iterative approaches. For Sci 57:435–447
Xunta de Galicia (2017) PLADIGA: Memoria. http://mediorural.xunta.gal/fileadmin/arquivos/forestal/pladiga/2017/2_MEMORIA.pdf. Accessed 19 Dec 2022 17:41:37