0
$\begingroup$

The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes $2^n$ steps for $n$ cities.

According to Wikipedia, the largest instance solved so far consists of $n=85,900$ cities and that it only took 1.5 years in 2006 to solve it.

How can that be? In complexity text books, it usually motivates the topic by stating that even for much smaller $n$ it would take million of years to find an optimal solution via brute force. How can $2^{85,900}$ tours be checked in 1.5 years?

$\endgroup$
5
  • $\begingroup$ The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes $2^n$ steps for $n$ cities. The obvious algorithm actually takes time proportional to $n!$, though this can be improved. Real-life algorithms use heuristics which run a lot faster in practice, especially on instance which are not worst-case. $\endgroup$ Jan 9, 2022 at 14:01
  • $\begingroup$ I agree but they claim that it is an optimal solution and not a heuristical / non-optimal solution. Am I wrong that for for such an optimal solution all possible tours need to be checked? (I also agree that trivial instances might be solved more easily, but this a real world 85,900 cities instance, I doubt that it is being used as a benchmark if it could be solved trivially). $\endgroup$ Jan 9, 2022 at 14:22
  • $\begingroup$ It is an optimal solution, and you are wrong that you have to check all possible tours. These heuristics work differently, and perform much better in practice. Their worst case complexity is unclear, but mostly irrelevant. $\endgroup$ Jan 9, 2022 at 14:28
  • $\begingroup$ But how does a heuristic knows that it found an optimal solution without an exhaustive search? Neither any metsheuristic nor a specialized heuristic such as Christofides can know this. Via B&B you can track the gap but this is still exponential (but potentially less than 2^n for practical instances). $\endgroup$ Jan 9, 2022 at 14:35
  • $\begingroup$ You’ll have to take a look at the actual heuristic. Is just like SAT solvers, which don’t have to run in time $2^n$. $\endgroup$ Jan 9, 2022 at 14:53

2 Answers 2

2
$\begingroup$

You are asking about a very specific instance of the problem and the solution was published as a paper. If you're really interested you should read that.

The solution itself was done with linear programming relaxation techniques and branch-and-bound. There is also a proof which is 32 MB in size when not compressed.

The proof itself basically gives you a lot of inequalities for the LP instance and then for some of them proves (even by brute force) the soundness in this example. This should give you a lower bound of about 142,381,678.2 and you can relax the original problem to just 265,259 edges. Then using branch-and-bound you just need to check this much smaller instance and you can cut anything with the path being longer than the original solution, 142,382,641.

The paper is from 2008 and the authors checked the proof (just checked, not solved the original problem; solution took 136 CPU years) in about 570 hours, so if you have a reasonably strong computer this should be computable in a few days now.

To exactly answer your question, you can use LP and its dual problem to make upper and lower bounds on the solution. If you get good enough equalities for a given problem, you can reduce the instance dramatically.

$\endgroup$
1
$\begingroup$

They didn't use brute force to solve it. They used a smarter method than brute force. I think they used algorithms that don't have any theoretical guarantee that they'll work well on all graphs, but happened to be good enough on that particular graph.

Taken literally, the notion of "the largest instance of travelling salesman problem ever solved" is nonsense. I can easily invent an instance of TSP with one million nodes where I already know the answer, and then solve it immediately (because I know the answer); or invent an easy instance on one million nodes, and then solve it immediately. So I suspect Wikipedia's summary is leaving out important details. As always, don't rely on secondary sources (like Wikipedia or an encyclopedia); instead, follow their citations to the primary source where that claim comes from, and read it to understand more about what is being said.

$\endgroup$
1
  • $\begingroup$ An example would be one million cities or ten million cities arranged at equal distances around a circle. $\endgroup$
    – gnasher729
    Jan 11, 2022 at 21:58

Your Answer

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

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