ALGORITMO GENÉTICO PARA RESOLUÇÃO HEURÍSTICA DO PROBLEMA DO NÚMERO DE QUEIMA

O Problema do Número de Queima (Burning Number Problem - BNP) consiste em determinar o menor número de iterações necessárias para que todos os vértices de um grafo sejam queimados. Neste trabalho, utiliza-se uma formulação inteira baseada em cobertura, cuja relaxação linear fornece limitantes inferiores, enquanto um algoritmo genético do tipo BRKGA produz limitantes superiores. A abordagem foi avaliada em grafos caminho e em instâncias da literatura. Os resultados validam a formulação nos grafos caminho e mostram que o BRKGA produz limitantes superiores competitivos, contribuindo para reduzir o espaço de busca da formulação inteira.