Wildfire Suppression: Complexity, Models, and Instances
This work addresses wildfire management, a critical issue for environmental and safety agencies, by providing theoretical insights and improved methods, though it is incremental in advancing existing computational approaches.
The paper tackles the problem of allocating wildfire suppression resources over time on a landscape graph to slow fire propagation, proving NP-completeness for related variants, proposing a new MIP formulation that achieves state-of-the-art results, and introducing a physics-grounded instance generator to benchmark algorithms.
Wildfires cause major losses worldwide, and the frequency of fire-weather conditions is likely to increase in many regions. We study the allocation of suppression resources over time on a graph-based representation of a landscape to slow down fire propagation. Our contributions are theoretical and methodological. First, we prove that this problem and related variants in the literature are NP-complete, including cases without resource-timing constraints. Second, we propose a new mixed-integer programming (MIP) formulation that obtains state-of-the-art results, showing that MIP is a competitive approach contrary to earlier findings. Third, showing that existing benchmarks lack realism and difficulty, we introduce a physics-grounded instance generator based on Rothermel's surface fire spread model. We use these diverse instances to benchmark the literature, identifying the specific conditions where each algorithm succeeds or fails.