Texto completo
| |
| Autor(es): |
Elder Magalhães Macambira
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 1997-06-06 |
| Membros da banca: |
Cid Carvalho de Souza;
Yoshiko Wakabayashi;
João Meidanis;
Ricardo Dahab
|
| Orientador: | Cid Carvalho de Souza |
| 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. (AU) | |
| Processo FAPESP: | 96/00884-9 - Uma abordagem de programacao linear inteira para o problema da clique maxima com peso nas arestas. |
| Beneficiário: | Elder Magalhaes Macambira |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |