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.
The game was developed as a free educational tool for introducing students to the power of optimization. In order to play the game, you will need to be logged in to your Gurobi account.
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 [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.
Figure 1: The critical node detection problem. Orange lines represent possible connections between node pairs (potential fire spread paths)
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|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.
Figure 2 – Forest landscapes can be depicted as a network of nodes and arcs on which the critical node detection MIP is solved
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.
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.
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
Cookie
Duration
Description
BIGipServersj02web-nginx-app_https
session
NGINX cookie
cookielawinfo-checkbox-advertisement
1 year
Set by the GDPR Cookie Consent plugin, this cookie is used to record the user consent for the cookies in the "Advertisement" category .
cookielawinfo-checkbox-analytics
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional
11 months
The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
CookieLawInfoConsent
1 year
Records the default button state of the corresponding category & the status of CCPA. It works only in coordination with the primary cookie.
elementor
never
This cookie is used by the website's WordPress theme. It allows the website owner to implement or change the website's content in real-time.
viewed_cookie_policy
11 months
The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
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.
Cookie
Duration
Description
__cf_bm
30 minutes
This cookie, set by Cloudflare, is used to support Cloudflare Bot Management.
_mkto_trk
2 years
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.
bcookie
1 year
LinkedIn sets this cookie from LinkedIn share buttons and ad tags to recognize browser ID.
bscookie
1 year
LinkedIn sets this cookie to store performed actions on the website.
doc_langsBB
1 year
Documentation system cookie
doc_version
1 year
Documentation system cookie
lang
session
LinkedIn sets this cookie to remember a user's language setting.
lidc
1 day
LinkedIn sets the lidc cookie to facilitate data center selection.
UserMatchHistory
1 month
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.
Cookie
Duration
Description
_gat_UA-5909815-1
1 minute
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.
Cookie
Duration
Description
_an_uid
7 days
6Sense Cookie
_ga
2 years
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.
_gcl_au
3 months
Provided by Google Tag Manager to experiment advertisement efficiency of websites using their services.
_gd_session
4 hours
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.
_gd_visitor
2 years
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.
_gid
1 day
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.
6suuid
2 years
6Sense Cookie
AnalyticsSyncHistory
1 month
No description
CONSENT
2 years
YouTube sets this cookie via embedded youtube-videos and registers anonymous statistical data.
dj
10 years
DemandJump cookie
djaimid.a28e
2 years
DemandJump cookiean
djaimses.a28e
30 minutes
DemandJump cookie
li_gc
5 months 27 days
LinkedIn Cookie
ln_or
1 day
LinkedIn Cookie
vuid
2 years
Vimeo installs this cookie to collect tracking information by setting a unique ID to embed videos to the website.
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Cookie
Duration
Description
__adroll
1 year 1 month
This cookie is set by AdRoll to identify users across visits and devices. It is used by real-time bidding for advertisers to display relevant advertisements.
__adroll_fpc
1 year
AdRoll sets this cookie to target users with advertisements based on their browsing behaviour.
__adroll_shared
1 year 1 month
Adroll sets this cookie to collect information on users across different websites for relevant advertising.
__ar_v4
1 year
This cookie is set under the domain DoubleClick, to place ads that point to the website in Google search results and to track conversion rates for these ads.
_fbp
3 months
This cookie is set by Facebook to display advertisements when either on Facebook or on a digital platform powered by Facebook advertising, after visiting the website.
_te_
session
Adroll cookie
fr
3 months
Facebook sets this cookie to show relevant advertisements to users by tracking user behaviour across the web, on sites that have Facebook pixel or Facebook social plugin.
IDE
1 year 24 days
Google DoubleClick IDE cookies are used to store information about how the user uses the website to present them with relevant ads and according to the user profile.
test_cookie
15 minutes
The test_cookie is set by doubleclick.net and is used to determine if the user's browser supports cookies.
VISITOR_INFO1_LIVE
5 months 27 days
A cookie set by YouTube to measure bandwidth that determines whether the user gets the new or old player interface.
YSC
session
YSC cookie is set by Youtube and is used to track the views of embedded videos on Youtube pages.
yt-remote-connected-devices
never
YouTube sets this cookie to store the video preferences of the user using embedded YouTube video.
yt-remote-device-id
never
YouTube sets this cookie to store the video preferences of the user using embedded YouTube video.
yt.innertube::nextId
never
This cookie, set by YouTube, registers a unique ID to store data on what videos from YouTube the user has seen.
yt.innertube::requests
never
This cookie, set by YouTube, registers a unique ID to store data on what videos from YouTube the user has seen.