Finding exact solutions for the Geometric Firefighter Problem in practice
| Autor: | Mauricio J. O. Zambon, Pedro J. de Rezende, Cid C. de Souza |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
General Computer Science Computer science 0102 computer and information sciences 02 engineering and technology Disjoint sets Construct (python library) Management Science and Operations Research 01 natural sciences Set (abstract data type) 010201 computation theory & mathematics Modeling and Simulation Polygon 0202 electrical engineering electronic engineering information engineering Benchmark (computing) 020201 artificial intelligence & image processing Point (geometry) Integer programming |
| Zdroj: | Computers & Operations Research. 97:72-83 |
| ISSN: | 0305-0548 |
| DOI: | 10.1016/j.cor.2018.05.003 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect