The Traveling-Salesman Problem and Minimum Spanning Trees

TLDR

The authors aim to advance symmetric traveling‑salesman problem solutions by leveraging 1‑trees and a family of lower bounds w(π). They employ 1‑trees, a distance‑transformation c_ij→C_ij+π_i+π_j, column‑generation and ascent techniques, and a branch‑and‑bound framework that uses w(π) to guide the search. They prove that the maximum of w(π) equals the optimal tour cost C* precisely when a related linear program has an integer optimum, and demonstrate efficient computation of this bound via the proposed methods.

Abstract

This paper explores new approaches to the symmetric traveling-salesman problem in which 1-trees, which are a slight variant of spanning trees, play an essential role. A 1-tree is a tree together with an additional vertex connected to the tree by two edges. We observe that (i) a tour is precisely a 1-tree in which each vertex has degree 2, (ii) a minimum 1-tree is easy to compute, and (iii) the transformation on “intercity distances” c ij → C ij + π i + π j leaves the traveling-salesman problem invariant but changes the minimum 1-tree. Using these observations, we define an infinite family of lower bounds w(π) on C*, the cost of an optimum tour. We show that max π w(π) = C* precisely when a certain well-known linear program has an optimal solution in integers. We give a column-generation method and an ascent method for computing max π w(π), and construct a branch-and-bound method in which the lower bounds w(π) control the search for an optimum tour.