Finding exact solutions for the Geometric Firefighter Problem in practice

摘要

In the Geometric Firefighter Problem (GFP), one aims 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 of the barrier. In this work, we consider the case where the initial set of barriers is comprised of rectilinear chords of the polygon. We present an Integer Programming (IP) model employed to solve the GFP to optimality along with procedures for preprocessing the instances, including primal algorithms and methods to reduce the problem size, as these constitute an essential step for solving harder instances. Moreover, we report on extensive experimental results that show that our IP model is an order of magnitude faster than the previous state-of-the art algorithm for the GFP. To further strain our algorithms, we introduce a new set of instances based on US national forests, which proved to be noticeably harder to solve than the previously available benchmark. An extended report on our experimental findings is presented along with a discussion that includes a restricted case where the constructed barriers must have pairwise disjoint interiors. (C) 2018 Elsevier Ltd. All rights reserved.