4
$\begingroup$

What is the efficiency of Concorde TSP solver program. And is it have any weaknesses? I build my own exact solver and I want to compare it to Concorde. What would be the best way to do this?

$\endgroup$
3
  • 1
    $\begingroup$ In the worst case, the runtime will be exponential -- I think internally it uses (I)LP solvers. You could look at the benchmarks listed, and run both Concorde and your own solver on the same computer to get comparable results. It will be extremely difficult to beat a highly optimized state of the art solver with something you can roll yourself in any decent time, but it is fun :-) $\endgroup$ – Juho Oct 22 '13 at 13:40
  • $\begingroup$ @Juho As I understood its hard getting in to his worst case, since he been able to solve inputs of thousands cities. Exponential solution will blow up already at 20 as for best known complex for this is O(N^2 2^N). 20 will be more then 20M tests. And yet concord doing thousands in minutes. So I can't just run a random compares on my pc. $\endgroup$ – Ilya Gazman Oct 22 '13 at 13:53
  • $\begingroup$ But the size of an instance doesn't imply hardness. The solver probably employs clever heuristics and tricks that work well for many cases. Perhaps you need to find instances that you can still in some reasonable time, and then run those on Concorde. Other than that, I guess you should think what is it that you want to benchmark exactly. $\endgroup$ – Juho Oct 22 '13 at 13:58
3
$\begingroup$

In the paper "Evolving L-Systems as an intelligent design approach to find classes of difficult-to-solve Traveling Salesman Problem instances" by Farhan Ahammed and Pablo Moscato, the authors show how to build instances which causes Concorde to run in its worst-case time.

So, you may compare your solver with Concorde on instances generated that way, besides comparing on randomly generated instances and/or specific test-case instances.

Here is the paper's abstract:

The technique of computationally analysing a program by searching for instances which causes the program to run in its worst-case time is examined. Concorde [2], the state-of-the-art Traveling Salesperson Problem (TSP) solver, is the program used to test our approach. We seed our evolutionary approach with a fractal instance of the TSP, defined by a Lindenmayer system at a fixed order. The evolutionary algorithm produced modifications to the L-System rules such that the instances of the modified L-System become increasingly much harder for Concorde to solve to optimality. In some cases, while still having the same size, the evolved instances required a computation time which was 30,000 times greater than what was needed to solve the original instance that seeded the search. The success of this case study shows the potential of Evolutionary Search to provide new test-case scenarios for algorithms and their software implementations.

$\endgroup$
0
$\begingroup$

Concorde works with symmetric instances of the TSP, that is, where the distance from city A to city B is the same as the distance from B to A. To solve an asymmetric instance with Concorde one would need to reduce the problem to a symmetric instance by node splitting. Targeting the asymmetric TSP directly is one possibility to make large improvements on Concorde's performance.

$\endgroup$
2
  • 1
    $\begingroup$ I think he is just asking how to compete his program against Concorde, not how to improve Concorde. $\endgroup$ – Realz Slaw Oct 22 '13 at 14:36
  • $\begingroup$ From his earlier posts, he's restricting to Euclidean TSP, anyway, so he's only considering symmetric cases. $\endgroup$ – David Richerby Oct 22 '13 at 16:35

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.