Concorde is a code for solving symmetric TSPs using branch-and-bound and problem specific branch-and-cut techniques http://www.math.uwaterloo.ca/tsp/concorde.html. I was wondering does Concorde solver can guarantee to solve the TSP to optimality in polynomial time. If yes how can we prove that ....knowing that I applied Concord solver and CPLEX solver I found that Concord could find optimal solutions for n=46 vertices in less than one second...
Dear Khelifa Meriem,
I suggest you to see links and attached files on topic.
Generating subtour elimination constraints for the TSP from pure ...
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5480099/
arXiv:1803.09621v2 [cs.LG] 15 Feb 2019
https://arxiv.org/pdf/1803.09621
Operations Research for Unmanned Systems
https://books.google.dz/books?isbn=1118918940
Neural Combinatorial Optimization with Reinforcem https://arxiv.org/pdf/1611.09940
Improving the State of the Art in Inexact TSP Solving using Per ...
https://www.cs.ubc.ca/~larsko/papers/tsplion.pdf
Best regards
"Yes" on the first question, "No" on the second. No-one knows whether TSP is solvable in polynomial time and/or space - the jury is still out.
- Badges
- Science topic