Utilização de desigualdades válidas baseadas em condições de otimalidade na construção de algoritmos heurísticos para o problema do corte máximo.

Abstract

The Max-Cut problem consists of partitioning a set of n nodes into two subsets so that the sum of the edges between the subsets is large as possible. This Course Completion Paper presents 4 new versions of heuristics algorithms, based on Genetic Algorithm and Simulated Annealing, which use a set of valid inequalities in their structure. To the best of our knowledge, we are the first to use valid inequalities in the construction of metaheuristics for the Max-Cut Problem. The results of the computational experiments show that the use of these inequalities causes the algorithms to obtain better results than the classical version, that is, without the inequalities and also, in some cases, competitive with the state of the art for Max Cut.