The linked post mentions a previous post [1] where he mentions that proving you have the optimal path doesn&#x27;t always require N! cost:<p>&gt; <i>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.</i><p>Note the &quot;provably&quot; before &quot;optimal solution&quot;.<p>1: <a href="http:&#x2F;&#x2F;mat.tepper.cmu.edu&#x2F;blog&#x2F;?p=6995" rel="nofollow">http:&#x2F;&#x2F;mat.tepper.cmu.edu&#x2F;blog&#x2F;?p=6995</a>