Premium
A matheuristic for the firefighter problem on graphs
Author(s) -
Ramos Natanael,
de Souza Cid Carvalho,
de Rezende Pedro Jussieu
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12638
Subject(s) - computer science , heuristics , integer programming , metaheuristic , interoperation , mathematical optimization , speedup , algorithm , mathematics , parallel computing , interoperability , operating system
In this paper, we describe a computational study conducted on The Firefighter Problem ( FFP ), which models fire spreading and containment in a graph. Once the fire breaks out on a set of vertices, the goal is to save as many vertices as possible with limited resources. Practical applications of the FFP occur in areas such as disease control and network security. The FFP is NP‐hard and heuristics have been proposed earlier. Our main contributions include improvements to an existing integer linear programming formulation that led to an average speedup of two to compute exact solutions. Moreover, we developed a novel matheuristic, a technique based on the interoperation between metaheuristics and mathematical programming. We performed extensive experiments on public benchmarks both for parameter tuning and for comparison of our results with those from the literature. A rigorous statistical analysis shows that our new matheuristic outperforms the existing approaches.