The traveling-salesman problem and minimum spanning trees: Part II

The relationship between the symmetric traveling-salesman problem and the minimum spanning tree problem yields a sharp lower bound on the cost of an optimum tour. An efficient iterative method for approximating this bound closely from below is presented. A branch-and-bound procedure based upon these considerations has easily produced proven optimum solutions to all traveling-salesman problems presented to it, ranging in size up to sixty-four cities. The bounds used are so sharp that the search trees are minuscule compared to those normally encountered in combinatorial problems of this type.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.This research has been partially supported by the National Science Foundation under Grant GP-25081 with the University of California. Reproduction in whole or in part is permitted for any purpose of the United States Government.