A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation

In 1970 Held and Karp introduced the Lagrangean approach to the symmetric traveling salesman problem. We use this 1-tree relaxation in a new branch and bound algorithm. It differs from other algorithms not only in the branching scheme, but also in the ascent method to calculate the 1-tree bounds. urthermore we determine heuristic solutions throughout the computations to provide upperbounds. We present computational results for both a depth-first and a breadth-first version of our algorithm. On the average our results on a number of Euclidean problems from the literature are obtained in about 60% less 1-trees than the best known algorithm based on the 1-tree relaxation. For random table problems (up to 100 cities) the average results are also satisfactory.