Configurações do Solver Gurobi e seu Efeito no Desempenho Computacional do TSP

Vol 57, 2025 - 340194
Resumo Estendido
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O Problema do Caixeiro Viajante (TSP, do inglês Travelling Salesman Problem) é um problema clássico de otimização combinatória amplamente utilizado como benchmark para métodos heurísticos e exatos. Ele determina o ciclo Hamiltoniano de menor custo em um grafo completo. Este trabalho analisa o impacto das configurações do solver Gurobi na resolução do TSP por meio de uma análise univariada, considerando parâmetros como presolve, geração de cortes, heurísticas e MIPFocus. Os experimentos foram conduzidos em instâncias da TSPLIB de pequeno e médio porte, variando-se um parâmetro enquanto os demais permanecem em seus valores default. O desempenho foi avaliado pelo tempo computacional. Os resultados indicam ganhos pontuais, com melhorias mais expressivas em instâncias pequenas ao desativar cortes e maior relevância de mipfocus_2 em instâncias médias. De forma geral, o efeito da parametrização é não linear e dependente das características das instâncias, reforçando a importância de abordagens adaptativas baseadas em meta-aprendizado.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Instituto Tecnológico de Aeronáutica (ITA)
  • 2 Instituto Tecnológico de Aeronáutica
Eixo Temático
  • OD - Otimização Discreta
Palavras-chave
Problema do Caixeiro Viajante
Solução Exata
Parametrização de Solver