2
$\begingroup$

i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum.

But when i'm finished, i'd like to check my solution but i don't know how. So i thought about using a computer-program to find the optimal solution to see, if my solution is within the 3/2-range.

i am not quite sure, if this is really possible or how long it might take. if it would take less than a month, i think, it would be worth a try.

$\endgroup$
2
$\begingroup$

It should be no problem to solve this instance with an integer linear programming based approach. You could try the online interface to the Concorde TSP solver.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.