  This paper considers the budget constrained fuel treatment scheduling (BFTS)
problem where, in the context of wildfire mitigation, the goal is to inhibit
the potential of fire spread in a landscape by proper fuel treatment
activities. Given a time horizon represented by consecutive unit periods, the
landscape is divided into cells and represented as a grid graph where each cell
has a fuel age that increases over time and becomes old if no treatment is
applied in the meantime: this induces a potential high fire risk whenever two
contiguous cells are old. Cells fuel ages can be reset to zero under
appropriate fuel treatments but there is a limited budget for treatment in each
period. The problem calls for finding a suitable selection of cells to be
treated so as to minimize the presence of old contiguous cells over the whole
time horizon. We prove that problem BFTS is strongly NP-complete on paths and
thus on grid graphs and show that no polynomial time approximation algorithm
exists unless P = NP. We provide an enhanced integer linear programming
formulation of the problem with respect to the relevant literature that shows
up to be efficiently solved by an ILP solver on reasonably large size
instances. Finally, we consider a harder periodic variant of the problem with
the aim of finding a cyclic treatment plan with cycles of length T and propose
a matheuristic approach capable of efficiently tackling those instances where
an ILP solver applied to the ILP formulation runs into difficulties.
