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.
ACESSO AO ARTIGO
http://hdl.handle.net/1843/RVMR-7L6METDocumentos 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