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.
Asked By : Toralf Westström
Answered By : Falk Hüffner
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12184
0 comments:
Post a Comment
Let us know your responses and feedback