Re:“American Scientist” Understands Nothing about the Travel...
by Strilanc on Tuesday April 26, 2016 @05:51PM
(#11576006)
The linked post mentions a previous post [1] where he mentions that proving you have the optimal path doesn't always require N! cost:
> If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. In fact, I would be really interested in knowing the smallest “real” instance that Concorde cannot solve in, say, one day, on a normal laptop computer.
> If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. In fact, I would be really interested in knowing the smallest “real” instance that Concorde cannot solve in, say, one day, on a normal laptop computer.
Note the "provably" before "optimal solution".
1: http://mat.tepper.cmu.edu/blog/?p=6995