O problema da arvore de custo minimo com k arestas:: reformulações e relaxação lagrangeana

AUTOR(ES)

Frederico Paiva Quintao

DATA DE PUBLICAÇÃO

2008

RESUMO

Dado um grafo G = (V,E), com custos nos vértices de V e nas arestas de E, o Problema da Árvore de Custo Mínimo com k Arestas (k-ACM) consiste em encontrar uma sub-árvore T em G com exatas k arestas, com o objetivo de que o custo de T seja mínimo. Este problema possui aplicacoções nas áreas de arrendamento de campos de petróleo, telecomunicações e roteamento, dentre outras. Neste trabalho, são propostas reformulações de Programação Inteira que se baseiam em uma transformação realizada sobre o grafo de entrada do problema. Após uma análise empírica do comportamento de algoritmos Branch-and-Bound que empregam as reformulações, foi proposta uma Relaxação Lagrangeana para uma delas. Esta Relaxação, que visa obter limites inferiores para o problema, foi integrada a uma heurística que se mostrou capaz de gerar limites superiores de qualidade para o mesmo.

ASSUNTO(S)

programação inteira. programação heuristica.

Documentos Relacionados

• Formulações e algoritmos sequenciais e paralelos para o problema da árvore geradora de custo mínimo com restrição de grau mínimo
• Relaxação lagrangeana com fixação de variáveis aplicada ao problema de sequenciamento em uma máquina
• Abordagem de refinamento iterativo para o problema da árvore geradora com número mínimo de vértices Branch
• MODELS AND ALGORITHMS FOR THE DIAMETER CONSTRAINED MINIMUM SPANNING TREE PROBLEM
• Alocação de unidades hidrelétricas no problema da programação da operação energética utilizando relaxação lagrangeana e lagrangeano aumentado