Please use this identifier to cite or link to this item:
|Title:||A matheuristic for the firefighter problem on graphs|
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|
|Appears in Collections:||IC - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.