Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/11422/12958
Especie: Dissertação
Título : Algoritmo relax-and-cut para o problema do conjunto independente máximo
Autor(es)/Inventor(es): Pereira, Matheus Caminha
Tutor: Lucena Filho, Abilio Pereira de
Resumen: 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 ã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.
Resumen: 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.
Materia: Algoritmo exato
Conjunto independente máximo
Materia CNPq: CNPQ::ENGENHARIAS
Programa: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Unidade de producción: Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Editor: Universidade Federal do Rio de Janeiro
Fecha de publicación: sep-2018
País de edición : Brasil
Idioma de publicación: por
Tipo de acceso : Acesso Aberto
Aparece en las colecciones: Engenharia de Sistemas e Computação

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
MatheusCaminhaPereira-min.pdf399.36 kBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.