The research group maintains an excellent webpage with many resources about the TSP . They have also developed an app (Concorde TSP)  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.
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.
Can you do the gaia run in less than 28,884,352.4 parsecs?
A good, related problem is graph isomorphism (check if two graphs are the same, just with the vertices in a different order). The complexity of this isn't known, it's between P and NO at the moment.
However, it's VERY hard to make hard instances. Basically all real world, or randomly generated, graphs can be solved in about O(n^3) time. There is significant research into just finding the hard cases.