GENETIC ALGORITHM FOR HEURISTIC RESOLUTION OF THE BURN NUMBER PROBLEM

The Burning Number Problem (BNP) aims to determine the minimum number of iterations required to burn all vertices of a graph. This work employs an integer programming formulation based on graph coverage, whose linear relaxation provides lower bounds, while a Biased Random-Key Genetic Algorithm (BRKGA) generates upper bounds. The approach was evaluated on path graphs and benchmark instances. The results validate the proposed formulation on path graphs and show that the BRKGA provides competitive upper bounds, helping to reduce the search space of the integer model.