Scientific Program > Talks by Speaker > Ben Salem Safa

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%.