Uma abordagem de programação linear inteira para o problema de clique maxima com peso nas arestas
Elder Magalhães Macambira
DISSERTAÇÃO
Português
T/UNICAMP M118a
Campinas, SP : [s.n.], 1997.
122f. : il.
Orientador: Cid Carvalho de Souza
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: Esta dissertação dá ênfase à abordagem poliedral para a resolução exata do Problema da Clique .Máxima com Peso nas Arestas. Dado um grafo completo não-dirigido Kn = (Vn, En), onde |Vn|= n, com um peso Cij associado a cada aresta (i,j) ? En, e um inteiro b, onde b = n; procuramos uma clique...
Ver mais
Resumo: Esta dissertação dá ênfase à abordagem poliedral para a resolução exata do Problema da Clique .Máxima com Peso nas Arestas. Dado um grafo completo não-dirigido Kn = (Vn, En), onde |Vn|= n, com um peso Cij associado a cada aresta (i,j) ? En, e um inteiro b, onde b = n; procuramos uma clique C em Kn cuja sorna dos pesos das arestas em C seja máxima e |C| = b. São apresentadas e discutidas diferentes formulações de programação linear inteira para o problema. Investigamos ainda a estrutura facial do poliedro associado ao problema realizando urna revisão bibliográfica das desigualdades conhecidas e introduzindo novas famílias de facetas. Por último, descrevemos os experimentos computacionais realizados com um algoritmo branch-and-cut e com urna metaheurística, ambos propostos neste trabalho. As maiores instâncias resolvidas de forma exata para este problema na literatura referem-se a grafos completos com no máximo 30 vértices. Neste trabalho, resolvemos exatamente instâncias para grafos com até 48 vértices e mostramos a força computacional para as novas desigualdades que introduzimos.
Ver menos
Abstract: Given a complete non-directed graph Kn = (Vn, En) on n nodes with weights on the edges and an integer b = n, we look for a clique C in Kn whose sum of the weights of the edges in e is maximum and such that |C| = b. We discuss on different integer programming formulations and investigate...
Ver mais
Abstract: Given a complete non-directed graph Kn = (Vn, En) on n nodes with weights on the edges and an integer b = n, we look for a clique C in Kn whose sum of the weights of the edges in e is maximum and such that |C| = b. We discuss on different integer programming formulations and investigate the facial structure of the polyhedron associated to the problem. New families of facet defining inequalities are introduced. Finally we describe our computational experiments with a branch-and-cut algorithm and a metaheuristic that we have proposed. The largest instances that are solved exactly in the literature refer to complete graphs with at most 30 nodes. In this work we solve to optimality instances for graphs with up to 48 nodes and we show the computational strength of the new inequalities we have introduced.
Ver menos
Uma abordagem de programação linear inteira para o problema de clique maxima com peso nas arestas
Elder Magalhães Macambira
Uma abordagem de programação linear inteira para o problema de clique maxima com peso nas arestas
Elder Magalhães Macambira
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra