[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.