Defesa de Mestrado de Alan Martins Silva

Título do Trabalho
Um estudo computacional do Problema do Brigadista Seletivo em Grafos
Candidato(a)
Alan Martins Silva
Nível
Mestrado
Data
Add to Calender 2019-08-23 00:00:00 2019-08-23 00:00:00 Defesa de Mestrado de Alan Martins Silva Um estudo computacional do Problema do Brigadista Seletivo em Grafos Sala 85 - IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
10:00
Local
Sala 85 - IC 2
Orientador(a)
Cid Carvalho de Souza
Banca Examinadora

* Titulares

Unidade/Instituição

Cid Carvalho de Souza

IC/UNICAMP

Edna Ayako Hoshino

FACOM/UFMS

Fabio Luiz Usberti

IC/UNICAMP

 

* Suplentes

Unidade/Instituição

Orlando Lee

IC/UNICAMP

Cleber Damião Rocco

FCA/UNICAMP

Resumo

O Problema do Brigadista Seletivo (PBS) é um modelo determinístico e em tempo discreto
para simulação da propagação e contenção de incêndios em um grafo. Uma instância do
problema contém um inteiro D, um grafo G(V, E) e dois subconjuntos de vértices B e T .
Em um momento inicial, apenas os vértices v ∈ B estão queimados. Então, um
processo iterativo tem início e ocorre em rodadas. Em cada rodada, no máximo D vértices
de V \ T podem ser defendidos e, após as defesas, o fogo se alastra, queimando todos os
vértices não defendido que são adjacentes à um vértice queimado. O processo termina
quando não existem vértices que ainda podem ser queimados. O objetivo é maximizar
o número de vértices em T que não estão queimados no fim do processo. O PBS é um
problema NP-Difícil e uma solução para ele é dada por uma sequência de defesas.
Nessa dissertação, nós apresentamos uma formulação de Programação Linear Inteira
(PLI) para o PBS baseada em uma formulação previamente introduzida na literatura
para um problema similar. São apresentadas também heurísticas gulosas construtivas,
procedimentos de busca local e algoritmos para o refinamento de soluções baseados no
modelo de PLI. Esses métodos são combinados em uma meta-heurística GRASP para o
PBS.
Diversos experimentos computacionais foram conduzidos com diferentes versões da
meta-heurística para avaliar a qualidade das suas soluções, incluindo comparações com as
soluções ótimas obtidas pelo modelo de PLI quando disponíveis.
Os resultados revelaram que diversas melhorias propostas neste trabalho são relevan-
tes. A maioria das soluções obtidas pela meta-heurística GRASP atingiram o valor ótimo
ou perderam apenas por algumas unidades.