The symmetric traveling salesman problem and edge exchanges in minimal 1-trees

In this article the effect of exchanging edges inside a minimal 1-tree with edges outside is analysed. In combination with an upper bound this analysis enables the elimination of variables in the symmetric traveling salesman problem. After discussion on a number of improvements for this analysis, the implementation is described in a traveling salesman algorithm based on the 1-tree relaxation. Computational results show the advantages of the edges exchanges for Euclidean problems (up to 120 cities) as well as for random table problems (up to 200 cities).