The basic method will be to break up the set of all tours into smaller and smaller subsets and to calculate for each of them a lower bound on the cost of the best tour therein.
—John Little et al., 1963.1
In the Dark Age of TSP cutting planes, between the work of Dantzig et al. in 1954 and Chvátal in 1973, researchers focused on a variety of alternative solution methods. Chief among these is the divide-and-conquer approach known as branch-and-bound, another general-purpose tool developed first in the context of the salesman. In state-of-the-art TSP software, branch-and-bound is combined with the cutting-plane method to produce a powerhouse capable of solving instances of the problem having thousands of cities.
The search ...