Don’t Go It Alone. Gurobi and Its Partners Provide the Continuum of Support You Need.
While the mathematical optimization field is more than 70 years old, many customers are still learning how to make the most of its capabilities. That’s why, at Gurobi, we have established the Gurobi Alliance partner network—a group of trusted partners who can support you in achieving your optimization goals.
Mathematical Optimization, Network Interdiction, and Forest Fire Prevention
Discover how mathematical optimization can be applied to reduce wildfire hazard in forest landscapes.
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 . 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 . 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 . The problem is NP-hard in general  but recent reformulations [4,5] helped decrease the problem size to O(|nodes|·|edges|) and O(|nodes|2) 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 . 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.
 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
 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.
 Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM. Detecting critical nodes in sparse graphs. Computers & Operations Research 2009; 36(7): 2193-2200.
 Shen S, Smith JC, Goli R. Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optimization 2012; 9(3): 172-188.
 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.
In this webinar, attendees will get a first look at our upcoming product release, Gurobi 10.0. We will summarize the performance improvements and highlight some of the underlying algorithmic advances, such as the network simplex algorithm, enhancements in concurrent LP, and optimization based bound tightening.
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
This cookie, set by Cloudflare, is used to support Cloudflare Bot Management.
This cookie is set by Marketo. This allows a website to track visitor behavior on the sites on which the cookie is installed and to link a visitor to the recipient of an email marketing campaign, to measure campaign effectiveness. Tracking is performed anonymously until a user self-identifies by submitting a form.
LinkedIn sets this cookie from LinkedIn share buttons and ad tags to recognize browser ID.
LinkedIn sets this cookie to store performed actions on the website.
Documentation system cookie
Documentation system cookie
LinkedIn sets this cookie to remember a user's language setting.
LinkedIn sets the lidc cookie to facilitate data center selection.
LinkedIn sets this cookie for LinkedIn Ads ID syncing.
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
A variation of the _gat cookie set by Google Analytics and Google Tag Manager to allow website owners to track visitor behaviour and measure site performance. The pattern element in the name contains the unique identity number of the account or website it relates to.
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
The _ga cookie, installed by Google Analytics, calculates visitor, session and campaign data and also keeps track of site usage for the site's analytics report. The cookie stores information anonymously and assigns a randomly generated number to recognize unique visitors.
Provided by Google Tag Manager to experiment advertisement efficiency of websites using their services.
This cookie is used for collecting information on users visit to the website. It collects data such as total number of visits, average time spent on the website and the pages loaded.
This cookie is used for collecting information on the users visit such as number of visits, average time spent on the website and the pages loaded for displaying targeted ads.
Installed by Google Analytics, _gid cookie stores information on how visitors use a website, while also creating an analytics report of the website's performance. Some of the data that are collected include the number of visitors, their source, and the pages they visit anonymously.
YouTube sets this cookie via embedded youtube-videos and registers anonymous statistical data.
5 months 27 days
Vimeo installs this cookie to collect tracking information by setting a unique ID to embed videos to the website.