Uma abordagem de programação inteira para o problema da triangulação de custo minimo

Autor(es)

Aminadab Pereira Nunes

• 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-11-27

Membros da banca

Cid Carvalho de Souza

• Orientador: Cid Carvalho de Souza

Resumo

Seja P um conjunto finito de pontos no plano e S(P) o conjunto de todos os segmentos de reta com extremos em P. Uma triangulação planar de P é um subconjunto maximal de S(P) tal que nenhum par de segmentos neste subconjunto se intercepta, exceto possivelmente nos extremos. Chamamos de triangulação de custo mínimo a triangulação planar cuja soma total dos comprimentos de seus segmentos de reta é mínimo dentre todas as triangulações planares de P. Não se conhece algoritmo polinomial que resolva o problema de determinar a triangulação de custo mínimo de um conjunto de pontos no caso geral, contudo, também não está provado tratar-se de um problema NP-difícil. Neste trabalho estamos interessados na resolução exata deste problema. Nossa abordagem é baseada em técnicas de programação inteira, em particular estudamos duas formulações distintas para o problema. A primeira formulação é baseada em uma equivalência entre o problema da triangulação de custo mínimo e uma versão restrita do problema do conjunto independente em um grafo. Além das desigualdades obtidas através da observação desta equivalência, mostramos como fortalecer a formulação através de certas propriedades geométricas do problema. Estudamos ainda uma outra formulação baseada principalmente no trabalho apresentado por Loera et. al em [dLHSS96]. Enquanto na primeira formulação as variáveis binárias estão associadas aos segmentos em S(P), nesta segunda formulação as variáveis binárias estão associadas aos triângulos com vértices em P. Os resultados computacionais que obtivemos mostram uma clara superioridade do segundo modelo. Para a primeira formulação implementamos um algoritmo branch-and-cut que nos permitiu resolver problemas de até 160 pontos (|P| = 160). Já para a segunda formulação a solução ótima da relaxação linear sempre foi inteira, o que nos permitiu resolver instâncias com até 1000 pontos (|P| = 1000) (AU)

• Processo FAPESP: 95/08929-9 - Resolução exata do problema da triangulação de custo mínimo: uma abordagem de programação linear inteira
• Beneficiário: Aminadab Pereira Nunes
• Modalidade de apoio: Bolsas no Brasil - Mestrado