alt Hacker NewsWould be nice if they could briefly describe the algorithm. Sounds like they’ve turned the TSP into an integer linear program that they can do branch and bound on, but I’m not sure.
Would be nice if they could briefly describe the algorithm. Sounds like they’ve turned the TSP into an integer linear program that they can do branch and bound on, but I’m not sure.
It's classic Lin Kernighan (http://webhotel4.ruc.dk/~keld/research/LKH/) for the primal heuristic, and optimality proof by Concorde for cutting plane generation and branching (https://www.math.uwaterloo.ca/tsp/book/index.html, or https://www.math.uwaterloo.ca/tsp/korea/computation.html for details specific to this instance), with CPLEX as the underlying LP solver.