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

Este trabalho trata do problema da máxima biclique balanceada com peso no vértice. Dado um grafo não direcionado com peso nos vértices, o objetivo do problema é encontrar uma biclique (subgrafo bipartite completo) balanceada que possua o máximo somatório dos pesos. Além de ser um problema NP-difícil, possui diversas aplicações preeminentes. Este artigo propõe uma meta-heurística GRASP com uso de uma busca local VND com três estruturas de vizinhança. A heurística proposta foi avaliada nas instâncias da literatura (DIMACS e BHOSLIB) e os resultados indicam que o algoritmo proposto, em comparação com o algoritmo exato CPLEX, foi capaz de encontrar todas as soluções ótimas conhecidas em um baixo tempo computacional.