Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Problemas de agrupamento são oriundos de várias áreas da ciência. No contexto
de teoria de grafos, pode-se gerar um agrupamento por meio de adições e
remoções de arestas de um grafo de modo que esse grafo seja composto de
subgrafos (clusters) completos disjuntos. Esse problema é conhecido
como o problema de edição de clusters. Entretanto, há casos em que
esses clusters podem se sobrepor. Há poucos trabalhos práticos na
literatura que consideram o problema de edição de clusters com
sobreposição. Com isso, neste trabalho, é proposta uma heurística híbrida para
esse problema. Essa heurística híbrida é composta por duas meta-heurísticas,
para gerar soluções do problema de edição de clusters, e de um modelo
por programação linear inteira mista, também proposto neste
trabalho, que é resolvido utilizando os clusters oriundos das
meta-heurísticas. Com os resultados obtidos nos testes realizados, pode-se
observar que a heurística híbrida pode gerar bons agrupamentos com
sobreposição.