Stronger bounds for the asymmetric traveling salesman problem
Safa Ben Salem  1, *@  , Ali Balma  2@  , Mehdi Mrad  3@  , Talel Ladhari  1@  
1 : Université de Tunis, Tunis Business School, Business Analytics and Decision Making  (BADEM)
P.O.Box 65, Bir El Kassaa, 2059, Tunis -  Tunisia
2 : Université de Tunis, Ecole Nationale Supérieure d'Ingénieurs de Tunis  (ENSIT)
Avenue Taha Hussein, 1008 Tunis -  Tunisia
3 : Raytheon Chair of Systems Engineering , Advanced Manufacturing Institute  (RCSE)
King Saud University, Riyadh 11421 -  Saudi Arabia
* : Corresponding author


In our study, we propose novel compact formulations of polynomial size for the asymmetric traveling salesman problem (ATSP) by using the Reformulation Linearization Technique (RLT) which allowed to obtain a stronger formulation than the best state-of-the-art models. In fact, we are looking for a polyhedron that is as close as possible to the convex hull of integer solutions to ATSP. Furthermore, we improve the best compact formulations of ATSP due to (Sherali, Sarin and Tsai, 2006)-known so far as being the strongest ones- by eliminating the redundant constraints and showing that they are equivalent and reducing them to a more compact equivalent formulation of smaller size. Moreover, we elaborate new dominance relationships between the newly devised formulations and the existing models. In addition to that, we perform some projections into the subspace defined by (Sherali, Sarin and Tsai, 2006) and derive new formulations, which turned out to be stronger also than the state-of-the-art models. We extend our work to the variant of the ATSP with precedence constraints. Computational experiments conducted on the benchmark instances TSPLIB confirm the better quality of the relaxations provided by our proposed formulation as the relative deviation between the lower bound and the optimal solution did not exceed 0.5%, whereas that of (Sherali, Sarin & Tsai, 2006) is about 1.5%.

Online user: 1 RSS Feed