Problema de Steiner em Grafos: Uma Experiência Numérica para Problemas de Médio Porte Utilizando Formulações Compactas de Multi-Fluxo
Autores
|
5874 |
2713,44
|
|
|
5875 |
2713,44
|
Informações:
Publicações do PESC
Título
Problema de Steiner em Grafos: Uma Experiência Numérica para Problemas de Médio Porte Utilizando Formulações Compactas de Multi-Fluxo
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
11/9/2015
Resumo
Este trabalho estuda o Problema de Steiner em Grafos, o qual é conhecidamente NP-difícil. No entanto, sua relaxação linear tem complexidade polinomial. Começamos definindo o problema e suas principais características. Apresentamos alguns métodos para resolver o problema já existentes na literatura. Em seguida, mostramos três formulações para o problema usando multi-fluxo, comparando-as antes de selecionar aquela que mais se aproxima do problema original. Realizamos alguns testes em diferentes instâncias para verificar a proximidade entre a relaxação e o problema original.
Abstract
This work studies the Steiner Tree Problem, which is known to be NP-hard. However, its linear relaxation has polynomial complexity. We begin by defining the problem and its major characteristics. We introduce some methods to solve the problem that already exist in literature. Then we show three formulations for the problem using multi-flow, comparing them before selecting the one that gets the closest to the original problem. We do some tests in different instances in order to check the closeness between the relaxation and the original problem.
Arquivo