Relax and cut: limitantes duais para o problema do caixeiro viajante

Abstract

The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP’s optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging, with the implementation of an algorithm that generates good dual bounds in low running time

O Problema do Caixeiro Viajante (PCV) é um problema clássico de Otimização Combinatória. Dado um conjunto de cidades e os custos de viagem entre cada par delas, o objetivo é encontrar um roteiro que passa em todas as cidades apenas uma vez e retorna à cidade de origem de menor custo total. O enunciado simples e resolução não trivial encantaram muitas pessoas ao longo dos anos. Na literatura são apresentadas diversas formulações matemáticas para o Problema do Caixeiro Viajante, além de comparações entre a qualidade da relaxação linear de tais formulações. A formulação clássica para o PCV é forte, porém possui um número exponencial de restrições, e é equivalente à formulação de multiproduto (multi-commodity), de ordem polinomial. O custo computacional para resolver a relaxação linear da formulação multiproduto é alto, incentivando a busca de novas formas de obter limitantes duais. Na literatura são propostos procedimentos para obtenção de limitantes duais para o PCV utilizando-se do método relax and cut, a partir do problema da designação (PD), dualizando inequações válidas que são violadas pela solução ótima do PD. Neste trabalho, propomos a aplicação do método relax and cut para a formulação do PCV com restrições de multiproduto. Os resultados obtidos no estudo computacional são encorajadores, com a implementação de um algoritmo que gera bons limitantes duais com baixo tempo computacional