The Geometric Firefighter Problem Project

Institute of Computing / University of Campinas

Citing this page

Use the BibTeX entry:

@misc{gfp-unicamp-page,
      author = {Mauricio J. O. Zambon and
                Pedro J. de Rezende and
                Cid C. de Souza},
      title = {The {Geometric Firefighter Problem} Project},
      year = {2017},
      howpublished = {\url{www.ic.unicamp.br/~cid/Problem-instances/Geometric-Firefighter}}
}

Abstract

Our objective is to develop algorithms for the Geometic Firefighter Problem (GFP) from preprocessing, to primal algorithms, to Integer Programming Models that enable solving the problem to optimality.

Problem Description

Proposed by Klein at al. [1], the GFP seeks to maximize the total area shielded from a fire that radiates from a point inside a polygonal region by constructing a subset of a given set of barriers. To decide which barriers to construct, a solution must take into account the speed of the circularly spreading fire and the barriers construction speed. A barrier is considered successfully constructed if the fire does not burn any still unconstructed point on it. In this work, we consider the case where the initial set of barriers is comprised of rectilinear chords of the polygon. We are also interested in the Disjoint Geometic Firefighter Problem (DGFP), which requires the constructed barriers to be pairwise interior disjoint.

The video below presents a visual example of the GFP and should help understand the problem.

Instances

Instances GFP solutions DGFP solutions
Art Gallery instances ([2], [3]) Complete set Complete set
U.S. national forests instances ([3]) Complete set Complete set

File format of the instances

Each instance file is formatted according to the following template:

<vf> <vb>
<nfires>
<firesourceslist>
<polygon>
<nbarriers>
<barrierslist>

The fields are detailed below. A point field is comprised of two floats representing the x and y coordinates, respectively. A segment field is composed of two points representing the endpoints of the line segment. A polygon type is described by an integer n, the number of points on the boundary of the polygon, followed by the n points defining the boundary.

Field Type Description
<vf> float the fire speed
<vb> float the barrier construction speed
<nfires> integer number of fire sources (currently 1 for all instances)
<firesourceslist> list of points list of fire sources (one by line)
<polygon> polygon the polygon boundary
<nbarriers> integer number of barriers
<barrierslist> list of segments list of barriers (one by line)

File format of the results

Each result file is formatted according to the following template:

<bestlb>
<bestub>
<nbarriers>
<solution>
The fields are detailed below.
Field Type Description
<bestlb> float the fire speed
<bestub> float the barrier construction speed
<nbarriers> integer number of barriers constructed
<solution> list of segments list of barriers constructed in the solution with the best known lower bound. The barriers are given in the order that they are to be constructed and the order of their endpoints determines the construction direction.

References

Contacts

Research supported by