Locating fuel breaks to minimise the risk of impact of wild fire Adán Rodrı́gueza Begoña Vitorianoa Ignacio Legueyb Marc Damagec a b Complutense University of Madrid (UCM) Polytechnic University of Madrid (UPM) c Real Melbourne Institute of Technology (RMIT) Extended abstract Abstract In order to respond the question “Where to locate fuel breaks?”, a peculiar location model is presented involving stochastic mixed integer nonlinear optimization, Bayesian networks and directional statistic inference. From a first sim- ple approximation to the large model, will be shown what motivates follow models and its complexity incorporated. Also, a case study with real data about Corsica region is presented. Keywords— stochastic programming, mixed integer programming, nonlinear programming, Bayesian inference 1 Introduction The problem consists in provide a tool to decide where to locate a FSZ (fight support zone) in order to minimize the global risk of fire. Discrete Location deals with the problem of deciding which site have to be used, from a finite set of possibilities, in order to optimize an objective. These site are usually plants or facilities. The Euclidean distance doesn’t use to be appropriate in some context, thence a network is used for model distances ([Garvey et al., 2015]). Insomuch as a FSZ consist on reduce the fire spread between two areas, FSZ problem can be seen as what arcs modify to minimize the global fire risk. We will see that the problem divides in two parts: measure the fire risk based on the probability of burn, and optimize what changes in the network minimize the risk of burn. c by the paper’s authors. Copying permitted for private and academic purposes. Copyright © In: G. Di Stefano, A. Navarra Editors: Proceedings of the RSFF’18 Workshop, L’Aquila, Italy, 19-20-July-2018, published at http://ceur-ws.org 2 Methodology 2.1 First approach The main idea is to split the region we want to consider in homogeneous areas, and define the connectivity between those areas with the probability of the fire to pass from one to other. With this idea in mind, the first problem is how to compute the probability of fire in a node known ignition probabilities and spread probabilities. Given a network (N, A) with N = {n1 , . . . , nm } A⊂N ×N being N the set of all nodes representing homogeneous areas of the land and A the set of directed edges connecting N . Also we denote as aij = (ni , nj ). The simplest way to compute the probability of fire in node ni (fi ) is assuming independence on those events, this is: 1 − f1 = (1 − ig1 ) (1 − f2 · a21 ) ... (1 − fm−1 · am−1,1 ) (1 − fm · am1 ) 1 − f2 = (1 − f1 · a12 ) (1 − ig2 ) ... (1 − fm−1 · am−1,2 ) (1 − fm · am2 ) .. .. .. .. .. .. . . . . . . 1 − fm−1 = (1 − f1 · a1m−1 ) (1 − f2 · a2m−1 ) ... (1 − igm−1 ) (1 − fm · amm−1 ) 1 − fm = (1 − f1 · a1m ) (1 − f2 · a2m ) ... (1 − fm−1 · am−1m ) (1 − igm ) Being fi the probability of fire in node ni , aij the probability of spread between node ni and node nj and igi the probability of ignition in node ni . Note 1. In order to facilitate the reading, we will use an abuse of notation. For example aij is defined as an arch of network (N, A), but in the previous system is used as a number (probability). Also we will see aij as an event (fire spread). In general, events and them probabilities are represented with same symbols, the context will give as the meaning in every case. With this formulation we can solve the problem to compute the probability of fire in a node with a nonlinear model (NLP). Adding binary variables, the model is transformed into a decision model. m 󰁛 min z = f i · vi i=1 s.a m 󰁜 1 − fi = (1 − igi ) · (1 − fj · aij · xij ) for i = 1, . . . , m j=1 (1) j∕=i m 󰁛 xij · cij ≤ B i,j=1 i∕=j fi ∈ [0, 1], xij ∈ {0, 1} (1) minimize expected loss cost, being vi an estimation of the losses if ni burns. Also, xij represents the decision of build a FSZ in arch aij and cij costs of locate a FSZ there. Locations of xij must be bounded by a budget B. In the case of a graph with cycles this approximation can be far from reality. Let us see an explanatory example. Example 1. Consider the simple graph G = (N = {n1 , n2 }, A = {a12 = (n1 , n2 ), a21 = (n2 , n1 )}) a12 n1 n2 a21 Now suppose a12 = a21 = 0.8, ig1 = 0.1 and ig2 = 0. The solution of the system 󰀝 1 − f1 = (1 − ig1 ) · (1 − f2 · a21 ) 1 − f2 = (1 − ig2 ) · (1 − f1 · a12 ) is 󰀝 f1 = 0.236 f2 = 0.189 In this case it’s easy to see this result is far from the correct solution. Note that the probability of the region represented by G having a fire is 0.1. Even more, if we consider the definition of event there is a fire in node ni as follows 󰀝 f1 = ig1 ∪ (f2 ∩ a21 ) (2) f2 = (f1 ∩ a12 ) ∪ ig2 i.e. fi burs if there is an ignition there or if its neighbor burns and fire can pass from it to fi . The equation Boolean system doesn’t have unique solution, see [Levchenkov, 2000]. This is, there a couple of sets fi∗ satisfying (2). 2.2 Stochastic One of the main problems is the existence of loops in G. In order to eliminate loops on the model we can consider wind scenarios. For every scenario the graph Gs to be optimize must be an acyclic graph. Let’s suppose there are four relevant types of wind in region: S = {n, s, e, w} and for every wind Gs is acyclic. Then the Stochastic optimization model based on (1) would be m 󰁛 min z = fis · vi i=1 s.a m 󰁜 󰀃 󰀄 for i=1,...,m 1 − fis = (1 − igi ) · 1 − fjs · asij · xij for s∈{n,s,e,w} j=1 (3) j∕=i m 󰁛 xij · cij ≤ B i,j=1 i∕=j fis ∈ [0, 1], xij ∈ {0, 1} Using meteorological data of the region, and fitting wind direction data on a density function, like in [Leguey et al., 2016], it is possible to provide a couple of wind scenarios, and provide a solution for the problem avoiding loop issues. The scenario are based on risky days, those days were humidity, temperature and wind velocity are favorable for fire appearance and propagation. Even without loops, the independence assumption is too hard. It can be proved that ran- dom variable F = {f1 , . . . , fm } is a Bayesian network. Using exact or approximation al- gorithms, it is possible to improve model formulation (3), this methodology is showed at [Cheng and Hadjisophocleous, 2009]. 3 Conclusion and future work Keeping the mind between the mathematical model and the real problem can be an effort, however, focusing only on one, the result could be useless. On one hand, this work faces several mathematical challenges. On the other hand, even being able to compute an exact solution for the complex model, it doesn’t have sense if the parameters are not realistic. Input parameters, ignition probabilities and spread probabilities, are based on historical fire database from Corsica firefighters, and meteorological information. In future works, it is planned to use, topography and vegetation data as well as expert knowledge. Finally, a sensitive analysis is required to claim imprecisions on the input data doesn’t change a lot optimize location. References [Cheng and Hadjisophocleous, 2009] Cheng, H. and Hadjisophocleous, G. V. (2009). The mod- eling of fire spread in buildings by bayesian network. Fire Safety Journal, 44(6):901–908. PT: J; NR: 23; TC: 15; J9: FIRE SAFETY J; PG: 8; GA: 477OZ; UT: WOS:000268529700009. [Garvey et al., 2015] Garvey, M. D., Carnovale, S., and Yeniyurt, S. (2015). An analytical framework for supply network risk propagation: A bayesian network approach. European Journal of Operational Research, 243(2):618. [Leguey et al., 2016] Leguey, I., Bielza, C., and Larranaga, P. (2016). Tree-structured bayesian networks for wrapped cauchy directional distributions. Advances in Artificial Intelligence, Caepia 2016, 9868:207–216. PT: S; CT: 17th Conference of the Spanish-Association-for- Artificial-Intelligence (CAEPIA); CY: SEP 14-16, 2016; CL: Salamanca, SPAIN; SP: Spanish Assoc Artificial Intelligence, BISITE, Univ Salamanca, Springer Team, AEPIA; NR: 25; TC: 0; J9: LECT NOTES ARTIF INT; PG: 10; GA: BG2XK; UT: WOS:000387750600019. [Levchenkov, 2000] Levchenkov, V. (2000). Solution of equations in boolean algebra. Compu- tational Mathematics and Modeling, 11(2):154–163.