Algoritmo GRASP-VND para o problema da máxima biclique balanceada com peso no vértice

Abstract

This work addresses the problem of "Maximum Balanced Weighted Vertex Biclique". In this context, the objective is to identify, in an undirected graph with vertex-weight attributes, a balanced biclique (complete bipartite subgraph) that maximizes the sum of the weights. This problem is notably complex, falling into the NP-hard class, and has significant relevance in various domains. We present an approach based on the GRASP meta-heuristic, complemented by a VND local search with neighborhood structures and a reduction technique tailored to the problem at hand. We evaluated the effectiveness of our proposal using widely recognized instances in the literature, such as DIMACS and BHOSLIB. The results obtained indicate that our algorithm outperforms the exact algorithm (CPLEX) in terms of efficiency, being capable of finding all 80 known optimal solutions in a reduced computational time. Finally, our approach demonstrated excellent results in more challenging instances, such as those from the KONECT dataset, encompassing large and sparse graphs. In these situations, the reduction technique proved highly effective, eliminating up to 99.78% of the vertices. This highlights the robustness and versatility of our methodology in solving the problem in various scenarios, with significant implications in related practical applications.