Mathematical Optimization, Network Interdiction, and Forest Fire Prevention

By Dr. Ed Klotz, Senior Mathematical Optimization Specialist, Gurobi Optimization

I live in Lake Tahoe, where forest fires pose a significant threat. Wildfires, while being a natural process in many natural ecosystems, can pose significant economic and social impacts in forested regions. While my house has never been in danger, major fires 50-100 miles or farther away have often resulted in poor air quality of hazardous levels or worse.

In the summer of 2022, my town was not significantly affected, but the summers of 2020 and 2021 were quite problematic. Many people in other locations in the Sierra Nevada have had to evacuate from their houses for extended periods of time, and local economies that depend on tourism were adversely affected long after the fires subsided.

Land management agencies invest significant resources into the prevention and suppression of fires in forest landscapes and yet the economic costs associated with wildfires continue to increase. On the positive side, I have seen the impressive work of the firefighters, driving by numerous locations where houses and structures were saved despite scorched trees all around them.

Given this background, I was pleased to learn at the INFORMS 2022 General Meeting of uses of mathematical optimization to help develop preventive strategies to reduce wildfire hazard in forest landscapes.  At the conference, I had a conversation with Dr. Denys Yemshanov of Natural Resources Canada, Canadian Forest Service, Great Lakes Forestry Centre. Specifically, his team considers a landscape management problem to find the best way to partition the forest landscape to minimize the chances of wildfires spreading through a particular landscape.

This can be achieved by maximally reducing the connectivity between patches with flammable fuels in the landscape. They model a forest landscape as a network of patches (nodes) with flammable forest fuels defining arcs where wildfires could spread between adjacent nodes.

They solve a critical node detection problem (see Figure 1) to find the locations of possible wildfire fuel treatments (such as prescribed burns or strategic thinning of forest stands) in order to minimize the risk of spread of forest fires in the area [1]. Preventive fuel treatments are intended to decrease the probability of fire spread and reduce fire severity and damage to human infrastructure. The nodes and arcs of the forest landscape network are determined by numerous factors, including the geography of the landscape, weather, and the potential of forest fires to spread between sites in the landscape network.

The concept of critical nodes characterizes the vulnerability and robustness properties of a network after a portion of nodes is removed, which, depending on the type of network, could be the result of natural disasters, adversarial attacks, or technical failures [2]. The critical node detection problem belongs to the family of network interdiction models which look for nodes in the network whose removal significantly reduces the network connectivity.  The concept has been applied in many disciplines, including IT security applications, transportation, social network analysis,  prevention of infections in hospitals, and disruption of illegal supply chains.

The critical node detection problem can be formulated as a MIP problem. The problem was first formulated using triangle inequalities that enforce transitive connectivity relationships between nodes in the network [3]. The problem is NP-hard in general [4] but recent reformulations [4,5] helped decrease the problem size to O(|nodes|·|edges|) and O(|nodes|²) variables and constraints, which enabled solving the practical problems using off-the-shelf commercial MIP solvers. Nevertheless, hard combinatorial complexity makes it difficult to find feasible solutions for models depicting large forest landscapes. Customized data decomposition techniques (such as node aggregation and the use of sophisticated forest fire behavior simulation models to delimit the areas where a wildfire is likely to spread to from a given site), help reduce the problem size.

Figure 2 illustrates, reading from left to right, how a forest landscape can be depicted as a network of nodes and arcs on which the critical node detection MIP is solved. Elevation, landscape, and possibly other factors such as local weather conditions are used to create a landscape network and estimate the directions a wildfire could spread through the landscape between all pairs of nodes.  Once the vectors of possible fire spread and their probabilities are estimated, arcs can be weighted based on the fire spread risk, and the critical nodes can be found.

Interdiction problems extend beyond critical node detection in networks. Other examples include binary knapsack interdiction, clique interdiction, matching interdiction, and project interdiction. More details can be found in [6]. These add to the long list of interesting and unexpected applications of mathematical optimization.

The use of mathematical optimization to help reduce the risk of forest fires is another example of the broad spectrum of industries and operations on which this AI technology has a positive impact.

References:

[1] Yemshanov D, Liu N, Thompson DK, Parisien M-A, Barber QE, Koch FH, et al. Detecting critical nodes in forest landscape networks to reduce wildfire spread. PLoS ONE 2021; 16(10): e0258060. https://doi.org/10.1371/journal.pone.0258060

[2] Walteros JL, Pardalos PM. Selected topics in critical element detection. In: Daras Nicholas J, editor: Applications of Mathematics and Informatics in Military Science; Springer Optimization and Its Applications, vol 71. Springer, New York, 2012. pp 9-26.

[3] Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM. Detecting critical nodes in sparse graphs. Computers & Operations Research 2009; 36(7): 2193-2200.

[4] Shen S, Smith JC, Goli R. Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optimization 2012; 9(3): 172-188.

[5] Veremyev A, Prokopyev OA, Pasiliao EL. An integer programming framework for critical elements detection in graphs. Journal of Combinatorial Optimization 2014a; 28 (1): 223-273.

[6] Smith C, Song Y. A survey of network interdiction models and algorithms. European Journal of Operational Research 2020: https://doi.org/10.1016/j.ejor.2019.06.024 https://www.sciencedirect.com/science/article/abs/pii/S0377221719305156.