Comment by moralestapia
19 hours ago
>Our computation produced a tour together with a proof that it is a shortest-possible route [...]
Proof nowhere to be found.
Waterloo-ers are nice people but I see an increasing trend of them just lying to get some cred. Come on guys, you don't have to follow the valley model that much.
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.
People really really really need to take some time to understand the concept of "burden of proof", so they can't stop making fools of themselves in public.
What are you actually expecting here?
The solution was found in a few days by the LKH TSP heuristic solver. They spent months (and decades of CPU time) using well-known techniques to bound the specific problem and prove that this was an optimal solution. It’s not something that you can synthesize to a page. They are literally announcing that they verified the heuristic-derived solution.
Consider it like any science, where folks can make shit up. But you can just run the bounding algorithms yourself, or prove they are incorrect.
2 replies →
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.
5 replies →
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.