EURO 2025 Leeds
Abstract Submission

549. Advancing Firefighter Games: Novel Integer Programming Formulations and the Cost-Value Model

Invited abstract in session MD-48: Applications of Location Methods, stream Locational Analysis.

Monday, 14:30-16:00
Room: Parkinson B09

Authors (first author is the speaker)

1. Marta Baldomero-Naranjo
Estadística e Investigación Operativa, Universidad de Cádiz
2. Jörg Kalcsics
School of Mathematics, University of Edinburgh
3. Antonio Manuel Rodriguez-Chia
Estadistica e IO, Universidad de Cádiz
4. Catriona Wedderburn
Royal (Dick) School of Veterinary Studies and Roslin Institute, University of Edinburgh

Abstract

In the Classical Firefighter game, a fire breaks out on some vertices of an undirected connected graph at time zero. At each subsequent time step, a fixed number of defenders can protect one vertex each from catching fire. Afterwards, the fire spreads from each burning vertex to every adjacent vertex that is neither burning nor defended. The game ends when the fire can no longer spread. The goal is to find a defence strategy (i.e., the location of defenders) that maximises the number of non-burning (saved) vertices. In this work, we first revisit the classical integer linear programming formulation and then present several improvements for it as well as two new formulations and tighter bounds on the maximal duration of the game.

Moreover, we relax the classical assumptions that all vertices have uniform values and costs, i.e., we allow vertices to have different values and costs for being defended. Furthermore, instead of a fixed number of defenders we are given a defence budget that we can spend each time step to defend the vertices. We call this the Cost-Value Firefighter game. We present three different integer linear programming formulations for the problem, along with a series of inequalities to strengthen the formulations as well as tight bounds on the maximal duration of the game.

Keywords

Status: accepted

Back to the list of papers