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

6: Cutting Planes

Starting from a solution worked out with strings on a model (which was in fact optimal), Dantzig, Fulkerson, and Johnson had nevertheless to face the possibility that billions of cuts might be needed.

—Alan Hoffman and Philip Wolfe, 1985.1

The linear-programming relaxations associated with the traveling salesman problem are wildly complex: the simplex method is no match for problems with constraints numbering in the billions. Fortunately, Dantzig, Fulkerson, and Johnson put forth an elegant idea for handling such complexity. Their cutting-plane method does not attempt to solve the full LP problem in a stroke, but rather computes LP bounds on a pay-as-you-go basis, generating specific TSP inequalities only as they are needed. ...

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