Logic-based Benders decomposition for wildfire suppression

DOI10.1016/J.COR.2023.106392MaRDI QIDQ6068720zbMATH OpenOpenAlexFDO

Authors M. G. Harris, Michael A. Forbes, Thomas Taimre

Publication date 13 November 2023

Published in Computers \& Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2209.01371

zbMATH Keywords

integer programmingBenders decompositionnetwork interdictionwildfires

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Abstract: We study the problem of locating fire suppression resources in a burning landscape in order to minimise the total area burned. The landscape is modelled as a directed graph, with nodes representing regions of the landscape, and arcs representing adjacency relationships. The fire spread is modelled using the minimum travel time principle. We propose a non-linear integer programming formulation and an exact solution approach utilising logic-based Benders decomposition. We benchmark the approach against a mixed integer program and an iterated local search metaheuristic from the literature. We are able to solve challenging instances to proven optimality in a reasonable amount of time.

Cites work

• scientific article; zbMATH DE number 1802810 (Why is no real title available?)
• scientific article; zbMATH DE number 2084694 (Why is no real title available?)
• scientific article; zbMATH DE number 1550909 (Why is no real title available?)
• A matheuristic for the firefighter problem on graphs
• A note on two problems in connexion with graphs
• A survey of network interdiction models and algorithms
• An attacker-defender model for analyzing the vulnerability of initial attack in wildfire suppression
• Bilevel knapsack with interdiction constraints
• Canonical Cuts on the Unit Hypercube
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• Fire containment in grids of dimension three and higher
• Generalized Benders decomposition
• Improved \(x\)-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks
• LP formulations of the shortest path tree problem
• Logic-based Benders decomposition
• Logic-based Benders decomposition for large-scale optimization
• Matching interdiction
• Maximizing the minimum source-sink path subject to a budget constraint
• Methods for removing links in a network to minimize the spread of infections
• Minimum vertex blocker clique problem
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Partitioning procedures for solving mixed-variables programming problems
• Removing Arcs from a Network
• Shortest-path network interdiction
• The Benders decomposition algorithm: a literature review
• The capacitated standard response fire protection siting problem: Deterministic and probabilistic models

This page was built for publication: Logic-based Benders decomposition for wildfire suppression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6068720)