We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK


93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > The compatible tour heuristic for the symmetric...
View graph of relations

« Back

The compatible tour heuristic for the symmetric traveling salesman problem

Research output: Working paper


Publication date2010
Place of publicationLancaster University
PublisherThe Department of Management Science
Number of pages0
Original languageEnglish

Publication series

NameManagement Science Working Paper Series


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.

Bibliographic note

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.

Related projects