[arutar]

I had the privilege to take a linear programming course with Bill, back when he still taught at the University of Waterloo. He spent some time discussing the TSP. TSP solving methods are very interesting, and the techniques used here essentially boil down to setting up an appropriate linear program (albeit with a large number of constraints relative to the number of nodes) and then using duality to obtain accuracy certificates.

The research group maintains an excellent webpage with many resources about the TSP [1]. They have also developed an app (Concorde TSP) [2] which provides really good graphical representation of the algorithm. There is an iOS app as well under the same name which has a nice interface.

[1]: http://www.math.uwaterloo.ca/tsp/ [2]: http://www.math.uwaterloo.ca/tsp/concorde/index.html

[knuthsat]

Although here they used a Lin Kernighan Helsgaun heuristic for most of the work.

The heuristic algorithm does not use linear programming. Maybe a bit of graph theory, like minimum spanning trees or harder Steiner trees, mainly for selecting edges for the LKH heuristic.

[arutar]

Thanks for your comment - that is good to know. I should have looked more carefully into the article before commenting.