Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Shortest-possible walking tour to 81,998 bars in South Korea

math.uwaterloo.ca

Post reply on HN
Print view View original

31–40 of 147 posts

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#31

Post by pkhuong »

bjornsing wrote: post #27

Would be nice if they could briefly describe the algorithm. Sounds like they’ve turned the TSP into an integer linear program that they can do branch and bound on, but I’m not sure.

It's classic Lin Kernighan (http://webhotel4.ruc.dk/~keld/research/LKH/) for the primal heuristic, and optimality proof by Concorde for cutting plane generation and branching (https://www.math.uwaterloo.ca/tsp/book/index.html, or https://www.math.uwaterloo.ca/tsp/korea/computation.html for details specific to this instance), with CPLEX as the underlying LP solver.

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#32

Post by inasio »

7e wrote: post #26
inasio wrote: post #25

Earlier quoted context omitted.

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.

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#33

Post by dumbfounder »

bjornsing wrote: post #28
OsrsNeedsf2P wrote: post #4

I'm impressed they found a dataset this hard, but not much harder. It's a delicate balance between beating the last Traveling Salesman hiscore (Netherlands), and never finishing your compute

Do we know they didn’t just prune problematic bars from the dataset until they found a one with a solution?

You and I don’t know. But this is hacker news so there is probably somebody here keeping them honest.

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#36

Post by rurban »

So NP is like P again. I learned in school 13 is the max and one of my algebra professors advanced it to 15 (in the 80ies). Then came 20, then came 20.000, this is 80k with proof, and at the World TSP page we see the record was 1m.

http://webhotel4.ruc.dk/~keld/research/LKH/

The biggest proven optimum is for 3178031 right now.

This should be really done with CUDA, not plain C, btw.

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#37

Post by omoikane »

OsrsNeedsf2P wrote: post #4

I'm impressed they found a dataset this hard, but not much harder. It's a delicate balance between beating the last Traveling Salesman hiscore (Netherlands), and never finishing your compute

In the "computations" page[1], the table lists the Netherlands computation as costing 97 CPU years with 6 months of elapsed time, while the Korean bars costs 44 years of CPU time and 3 months of elapsed time. I can't tell if the two problems were solved using the same hardware.

[1] https://www.math.uwaterloo.ca/tsp/korea/computation.html

Post reply on HN