I have a Traveling Salesman Problem instance. If I provide different permutations of the instance to the Concorde solver, can it produce different results? Can it provide the same result all the time with varying speed of computation for different permuations?
Dear Lahari Sengupta,
It seems to me that initialization is necessary, but it is better to check this through the consultation of the links and attached file on topic.
http://www.exatas.ufpr.br/portal/docs_degraf/paulo/Traveling_Salesman_Problem__Theory_and_Applications.pdf
http://www.math.uwaterloo.ca/tsp/concorde/gui/gui.htm
Article Exact algorithms and heuristics for the Quadratic Traveling ...
Article Planning Your Route: Where to Start?
Technical Report Concorde solver installation and use
Best regards
Hello Lahari,
Exact algorithms such as Concorde are designed to return "one" optimal solution. It is absolutely possible (and quite common) for a TSP instance to admit several distinct optimal solutions, especially when distances are integer. A new instance created by shuffling the order of the customers can easily lead to different algorithmic (e.g., branching) decisions in case of ties.
We also know that the behavior of branch-and-bound algorithms is quite sensitive to early decisions and parameters (sometimes a bad early branch choice can make the difference between solving the problem in 1 second or 1000 seconds). It is therefore not a surprise to observe significant changes of computational time for different permutations of the same instance. As a general rule of thumb, I recommend to analyze the behavior of exact algorithms on a large-enough set of benchmark instances (or permutations thereof) to identify significant effects.
Dear Lahari,
If your problems belongs to small size of TSP, the results are same but when their size are increased, two slolutions may be different (for example, they cannot obtain the optimum solutions and stop with different solutions).
- Badges
- Science topic