We consider the following natural heuristic for the Symmetric Traveling Salesman
Problem: solve the subtour relaxation, yielding a solution x*, and then find the best
tour x that is compatible with x*, where compatible means that every subtour elimination
constraint that is satisfied at equality at x* is also satisfied at equality at x.
We prove that finding the best compatible tour is NP-hard and show that the tour can
have a cost approaching 5/3 that of the optimal tour. We then describe a branch-and-cut
algorithm for computing the best compatible tour, and present extensive computational
results for TSPLIB instances. It turns out that, in practice, the tour can be found quickly
and is usually of very good quality.
This was eventually published as: M. Fortini, A.N. Letchford, A. Lodi & K.M. Wenger (2011) Computing compatible tours for the traveling salesman problem. Math. Program. Comput., 3(1), 59-78.