2
$\begingroup$

What is currently the exact method to solve the TSP which performs best on average regarding computation time?

$\endgroup$
2
  • 5
    $\begingroup$ The Concorde solver is the best there is: math.uwaterloo.ca/tsp/concorde/index.html. It uses a combination of heuristics, cuts, branching, and smart relaxations. $\endgroup$
    – mtanneau
    Jul 13, 2022 at 0:23
  • $\begingroup$ @mtanneau Thanks, I also stumbled about Concorde. What is the general strategy they are using? What MIP model do they base their solution mechanism on? $\endgroup$ Jul 13, 2022 at 12:13

2 Answers 2

3
$\begingroup$

I would say "it depends". If the instances you want to solve are small (up to, say, 10-12 nodes) then dynamic programming works wonders. If the problem is up to 30-40 nodes, you can get by using a general IP solver using a good model formulation. Above that, you need to either design your own branch and cut algorithm using problem specific cuts or figure out how to use Concorde.

Concorde is without a doubt the champion when it comes to large scale TSPs.

$\endgroup$
1
$\begingroup$

For small instances, i think the branch and cut will works well. You can try localsolver or concorde to prove optimality for bigger instances in reasonable time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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