Please use this identifier to cite or link to this item:
Type: Artigo
Title: A matheuristic for the firefighter problem on graphs
Author: Ramos, Natanael
de Souza, Cid Carvalho
de Rezende, Pedro Jussieu
Abstract: 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
Subject: Otimização combinatória
Country: Reino Unido
Editor: Wiley
Rights: Fechado
Identifier DOI: 10.1111/itor.12638
Date Issue: 2020
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000490364500002.pdf1.26 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.