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

AUTOR(ES)

Aminadab Pereira Nunes

DATA DE PUBLICAÇÃO

1997

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)

ASSUNTO(S)

otimização combinatoria algoritmos pesquisa operacional geometria

Documentos Relacionados

• Uma abordagem de programação linear inteira para o problema de clique maxima com peso nas arestas
• Formulações e algoritmos sequenciais e paralelos para o problema da árvore geradora de custo mínimo com restrição de grau mínimo
• Abordagem de refinamento iterativo para o problema da árvore geradora com número mínimo de vértices Branch
• O problema da arvore de custo minimo com k arestas:: reformulações e relaxação lagrangeana
• Uma abordagem evolutiva para o problema de custo médio a longo prazo com saltos não-observados