2 ms·

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

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.

pkhuong 1y ago
It's classic Lin Kernighan (http://webhotel4.ruc.dk/~keld/research/LKH/ 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 https://www.math.uwaterloo.ca/tsp/book/index.html, or https://www.math.uwaterloo.ca/tsp/korea/computation.html https://www.math.uwaterloo.ca/tsp/korea/computation.html for details specific to this instance), with CPLEX as the underlying LP solver.