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.