What is currently the exact method to solve the TSP which performs best on average regarding computation time?
$\begingroup$
$\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$– mtanneauJul 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$– J Fabian MeierJul 13, 2022 at 12:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
