Genetic Algorithms with Optimality Cuts to the Max-Cut Problem

• Pablo Luiz Braga Soares UFC
• Carlos Victor Dantas Araújo UNICAMP

Resumo

The MAX-CUT Problem involves dividing a set of n vertices in a weighted graph G = (V, E) into two subsets (S, S) in such a way that the sum of the weights between the subsets is maximized. This research introduces two heuristic methods that combine Genetic Algorithm, Tabu Search, and a set of optimality cuts, which are also proven in this work. To the best of our knowledge, we are the first to utilize these inequalities in conjunction with the genetic algorithm methodology to solve the MAX-CUT problem. Computational experiments using a benchmark set of 54 instances, ranging from 800 to 3000 vertices, demonstrate that the incorporation of optimality cuts is a crucial factor for our methodologies to compete effectively with six state-of-the-art approaches for the MAX-CUT problem and our genetic algorithm that incorporated optimality cuts in the population generation was able to improve the state-of-the-art value for the G51 instance and find the same solutions as the literature in 31 other instances.