The Firefighter Problem on Graphs - Benchmark Instances, by N. Ramos, C. C. de Souza and P. J. de Rezende

Citing this page:

    Use the BibTeX entry:

    @Misc{ffp-instances-page,
     author = {Natanael Ramos and Cid C. de Souza and Pedro J. de Rezende},
     title = {The Firefighter Problem on Graphs - Benchmark Instances},
     year = {2018},
     note = {{\sl www.ic.unicamp.br/\textasciitilde cid/Problem-instances/ffp}}
    }

Problem description

The Firefighter Problem (FFP) was first proposed in 1995 by Hartnell [6] as a deterministic discrete-time modeling of a fire propagation in graph theoretical terms. In this context, the spreading and containment of the fire is represented in an unweighted undirected graph \(G = (V , E)\) as an iterative process. In each iteration, \(D\) firefighters are available to combat the fire and a vertex of \(G\) can be in one of three states: untouched, burned or defended. Once a vertex is defended or burned, it remains so until the process has been completed. Initially, all vertices are untouched, except for a given nonempty subset \(B\) of vertices representing the fire outbreaks. Then, a series of 2-phase iterations takes place. In the first phase, at most \(D\) vertices are defended each of which by exactly one firefighter. In the subsequent phase, all vertices adjacent to burned ones and not yet defended are consumed by the fire. The process terminates when, in a iteration, no new vertex is burned in this second phase. The FFP aims at minimizing the number of vertices burned after the fire has been contained.

The pictures below show an example of the process of spreading and containment of the fire in one instance of the FFP with \(D = 1\) and \(B \leftarrow \{5\}\). On the first iteration, image (a) only the fire outbreak 5 is burned. On (b) the vertex 6 is defended by the only available firefighter and the vertices 2, 4 and 6 are burned since they are neighbors of 5 and were not defended. On (c) the fire is contained after the vertex 7 was defended and the vertices 1 and 3 were burned.

(a) Iteration 0

(b) Iteration 1

(c) Iteration 2

Input Instances

The instances are organized in compressed files, being each file named after the set that they come from: BBGRL from Blum et. al. [2]*, GBRL from García-Martínez et. al. [4] or GEN for the instances generated by us using the models from Erdös and Rényi [3] and Barabási and Albert [1].
The name of each instance is in the following pattern:

     <\(n\)>_<parameter>_<\(B \) description>_<model>_<count>.in

  • \(n\): Number of vertices.
  • parameter: Parameter used in the model that generate the respective instance, followed by its value. The parameters are: ep for the model of Gilbert [5] or the one from Erdös and Rényi [3], r for the geometric model of García-Martínez et. al. [4] and m in the case of the model by Barabási and Albert [1].
  • \(B\) description: How is defined the subset \(B\) of \(V\): 0 when it is the vertex of index 0 and degree when it is the vertex with highest degree.
  • model: Model used to generate the instance: erdos, gilbert, social (for the model of Barabási and Albert [1]), geom.
  • count: From the set of \(k\) instances generated with the same values of parameter and \(n\), a integer \(k' \in \{1, \ldots, k\}\) indicating which one is it.

File Format: Instances
Each instance consists of a graph, with the following format:

     <seed>
     <\(n\)>
     <\(m\)>
     <\(B\) description>
     <\(|B|\)>
     <\(B\)>
     <\(u\;v\)>

The seed is the one used in the pseudorandom number generator to create the respective instance. In the instances from the set BBGRL and GBRL, the seed is always 0, since it was not published by the authors. The values of \(n\) and \(m\) indicates the number of vertice and edges, respectively. In the following three lines are the \(B\) set descripition (as in the instance name), the size of it and its members, respectively. The remaining \(m\) lines are in the form \(u\;v\) indicating that there exists a edge between \(u\) and \(v\).

BBGRL instances-BBGRL.tar.bz2 (32K)
GBRL instances-GBRL.tar.bz2 (68K)
GEN instances-GEN.tar.bz2 (64K)

Results

The results are in csv files, each one corresponding to one of the set of instances. Each row of each file corresponds do the result of one instance. The columns in the file indicate the set of instances that they belong to, \(n\), \(D\), the name of the instance, the result obtained, the runtime and the seed used on the pseudorandom number generator.
BBGRL results-BBGRL.csv (86K)
GBRL results-GBRL.csv (166K)
GEN results-GEN.csv (224K)

The results were obtained with an implementation of the matheuristic in C++ compiled with the GCC compiler version 7.1.0, using -O3 as optimization level. As an ILP solver, the solver IBM ILOG CPLEX version 12.7.1 was used. We conducted the experiments on a computer with a processor Intel®Xeon®CPU E5-2420 with 12 cores of 1.90 GHz each and 32GB of RAM.
A different time limit was set for each set of instances, accordingly with the previous works on the FFP and due to hardware discrepancies. For the instances of the set BBGRL, this time limit was defined as \(n/6\), \(n/4.8\) seconds for the set GBRL and 10 minutes for the set GEN.

Optimal results for the sets BBGRL e GBRL with \(n \in \{50,100\}\):

BBGRL results-opt-BBGRL.csv (30K)
GBRL results-opt-GBRL.csv (58K)

Solution Files

For each instance, there is a corresponding solution file. The name of the file is in the following pattern:

     <\(n\)>_<parameter>_<\(B \) description>_<model>_<count><\(D\)>.sol

The content of each solution file is in the format:

     <\(v,t\)>

Where \(v\) indicates a defended vertex and \(t\) indicates in which iteration it was defended.

BBGRL solutions-BBGRL.tar.bz2 (32K)
GBRL solutions-GBRL.tar.bz2 (68K)
GEN solutions-GEN.tar.bz2 (64K)

Optimal solutions for the sets BBGRL e GBRL with \(n \in \{50,100\}\):

BBGRL solutions-opt-BBGRL.tar.bz2 (23K)
GBRL solutions-opt-GBRL.tar.bz2 (51K)

Acknowledgments

*We wish to thank Christian Blum for kindly provide the set of instances BBGRL.

This research was supported by grants from Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) #311140/2014-9, #304727/2014-8, #133728/2016-1.

References

Address

Natanael Ramos, Cid C. de Souza and Pedro J. de Rezende
Universidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: