Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275995
Type: TESE
Title: Uma abordagem de programação linear inteira para o problema de clique maxima com peso nas arestas
Author: Macambira, Elder Magalhães
Advisor: Souza, Cid Carvalho de, 1963-
Abstract: 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.

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.
Subject: Programação linear
Polidros
Algoritmos
Otimização combinatória
Programação (Matemática)
Language: Português
Editor: [s.n.]
Date Issue: 1997
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Macambira_ElderMagalhaes_M.pdf3.79 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.