18
$\begingroup$

The Traveling Salesman Problem is perhaps the most studied of all combinatorial optimization problems. There has been a lot work in solving TSP instances to provable optimality. Concorde solves very large instances to provable optimality, with the largest solved having 85,900 points. There is a 100,000 city problem that has not been solved to provable optimality. But there are some smaller instances not solved to optimality, with the smallest at 6732 cities. Is this the smallest "difficult instance"? Are there small TSPs that are hard for Concorde or other other optimization approaches to solve?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
13
$\begingroup$

There is a paper of Ahammed and Moscato on finding hard instances for Concorde using Lindenmeyer systems. They were able to find small instances with about 1500 cities that took (in 2011) more than 4 hours to solve.

One should probably add that "hard" always means "hard for some algorithm". So, for balance, here is a paper of Kate Smith-Miles & van Hemert studying hardness for variants of the Kernighan-Lin algorithm.

For more on the pitfalls of "hard" versus "easy" in the context of SAT, there's an excellent talk of Moshe Vardi where he concludes that "the 'easy-hard-easy' picture is patently wrong".

Improve this answer
$\endgroup$
8
$\begingroup$

There is a paper by Papadimitriou and Steiglitz here to construct instances, which are very hard for local searches to find optimal solution.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It would be interesting to know if LP+cut approaches can sort out those instances: the LP gives a global view but I would bet the LP fractions hedge the choices in each of the widgets. $\endgroup$
    – Michael Trick
    Jun 9, 2019 at 15:33
  • 1
    $\begingroup$ I can test this by a Branch-and-Cut to evaluate the performance of exact methods on these type of instances, I let you know about this @Michael. $\endgroup$
    – Majid
    Jun 9, 2019 at 22:08
1
$\begingroup$

Hard to Solve Instances of the Euclidean Traveling Salesman Problem provides awhole class of hard to solve small instances for the planar Euclidean TSP; the are also downloadable instances.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh very cool. This was known a year before I posed the question. I wonder if there has been anything since 2018? $\endgroup$
    – Michael Trick
    Jun 11 at 17:13

Your Answer

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

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