Hacker News Reader

Comment by moralestapia | Hacker News Reader

[flagged]

Not sure what you expected to get. The Concorde TSP solver is an exact solver that uses branch and bound search, it will return either a solution with a specified bound or the optimal bound. They provide the dataset and the solution they found (and I believe their solver is open source), if you don't believe them you can go ahead and find a better tour.

I also expected to get an actual proof.

Proof in this case is that the upper bound and the lower bound of the solver converged. This is not like a SAT solver where the solution itself can be trivially evaluated to verify the solution, it requires trusting that the solver does what it's supposed to be doing, similar to what happens when you solve a MILP with Gurobi or CPLEX.

You could still save the branch-and-bound tree, the LP problems solved at the tree nodes, the derivations of the LP cutting planes, and the LP solutions that together constitute the proof. Then you could in principle create an independent verifier for the branch-and-bound tree and cutting plane derivations, which could potentially be much more straightforward and simple code than the entire Concorde TSP solver, and wouldn't have so high performance requirements.

Is the solver guaranteed not to land in a local minima/maxima?

(I don't know)

But I would guess the answer is "no".

If you can prove, as they claim, that you have an algorithm that gives you the optimal solution (aside from the obvious, brute-forced one), you might be one stone throw away to make an argument for some P == NP, that would be HUGE.

But it seems that some people get offended when you tell them their perpetual motion machines are not real.

The branch-and-bound algorithm does provide a proven optimal solution. This does not mean that P=NP because the size of the proof is not bounded by a polynomial in the input size, and neither is the algorithm runtime. Also, Euclidean TSP is known to be easier than TSP on arbitrary graphs: there are polynomial-time approximation schemes that can produce solutions with an (1+epsilon) factor of the optimum in polynomial time, for any value of epsilon. Thus it is not surprising that a proof of full optimality can be constructed for some instances.

The solver generates a relaxed lower bound that indicates how far they could be from the global optimal solution. The moment that the lower bound improves enough to match a path they can guarantee that it's the global optimum

The code is here I think: http://webhotel4.ruc.dk/~keld/research/LKH/ although on another page they mention LKH-Merge and I'm not sure what merge is.

These claims are provisional. Until someone produces a better tour or a valid counter-proof, this stands as the best-known solution.

>Our computation produced a tour together with a proof that it is a shortest-possible route [...]

>These claims are provisional. Until someone produces a better tour or a valid counter-proof, this stands as the best-known solution.

Are we looking at the same website? Because those two are quite different things.

Reply on news.ycombinator.com