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?

$\endgroup$
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$
  • 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 '19 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 '19 at 22:08

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.