Algoritmo Relax-and-Cut para o Problema do Conjunto Independente Máximo
Autores
|
6632 |
2979,519
|
|
|
6633 |
2979,519
|
Informações:
Publicações do PESC
Propomos algoritmos exatos e heurísticos para o Problema do Conjunto Independente Máximo. Ao invés da formulação padrão do problema, que normalmente leva a limites de relaxação linear muito fracos, utilizamos uma reformulação muito mais forte, baseada numa cobertura de arestas por cliques. A reformulação é original e é aqui introduzida. Para resolvê-la, desenvolvemos um algoritmo do tipo Non Delayed Relax-and-Cut, um análogo Lagrangeano de um algoritmo de planos de corte. O algoritmo gera limites primais e duais para o problema. Isso é feito dualizando desigualdades válidas dinamicamente, à medida em que são violadas por soluções de Subproblemas Lagrangeanos. A seguir, num procedimento de warm start, desigualdades de clique (dualizadas dinamicamente durante a aplicação do algoritmo Relax-and-Cut) são agregadas à reformulação, que é então submetida, nessa forma reforçada, ao software CPLEX. O algoritmo Relax-and-Cut, atuando isoladamente e restrito apenas à dualização dinâmica de desigualdades de clique, conseguiu obter limites primais ou duais ótimos para 107 das 119 instâncias testadas. Por sua vez, o algoritmo exato, Relax-and-Cut-CPLEX, conseguiu obter certificados de otimalidade para 64 instâncias, três delas previamente em aberto há trinta anos. Além disso, conseguiu obter limites primais ou duais ótimos para 110 instâncias.
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.