O'Reilly logo

In Pursuit of the Traveling Salesman by William J. Cook

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

7: Branching

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.

Breaking Up

The search ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required