Algoritmo relax-and-cut para o problema do conjunto independente máximo

Abstract

Heuristic and exact algorithms are proposed for the Maximum Independent Set Problem. Instead of the standard formulation of the problem, which usually leads to very weak linear relaxation bounds, we use a much stronger reformulation, based on an edge clique cover. The reformulation is new and is introduced here. To solve it, we developed a Non Delayed Relax-and-Cut algorithm, a Lagrangian analog to a cutting plane algorithm. The algorithm generates primal and dual bounds for the problem. It does that while dynamically dualizing valid inequalities, as they become violated by solutions to Lagrangian Subproblems. Next, in a warm start procedure, clique inequalities (that were dynamically dualized throughout the Relax-and-Cut algorithm) are appended to the reformulation, which is then submitted, in that reinforced form, to solver CPLEX. The Relax-and-Cut algorithm, just by itself and restricted to dualizing only clique inequalities, was able to attain optimal primal or dual bounds for 107 of the 119 instances tested. On the other hand, the exact Relax-and-Cut-CPLEX algorithm obtained optimality certificates for 64 instances, three of them previously open for thirty years. Additionally, it also attained optimal primal or dual bounds for 110 instances.