Shortest-possible walking tour to 81,998 bars in South Korea • Hacker News Board

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

#51

Post by unnah » Thu, Apr 24, 2025, 6:33 AM UTC

inasio wrote: post #32

7e wrote: post #26

Earlier quoted context omitted.

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.

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

#52

Post by Animats » Thu, Apr 24, 2025, 6:35 AM UTC

If you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result?

The classic TSP approach is:

1. Hook up all the nodes in some arbitrary path.

2. Cut the path in two places to create three pieces.

3. Rearrange those three pieces in the six possible ways and keep the shortest.

4. Iterate steps 2-3 until no improvement has been observed for a while.

This is not guaranteed to be optimal, but for most real-world problems either finds the optimal result or is very close.

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

#53

Post by xmprt » Thu, Apr 24, 2025, 6:48 AM UTC

codemac wrote: post #45

lifthrasiir wrote: post #16

Earlier quoted context omitted.

That country has a population of 52 million, i.e. about 5 times Ohio.

Sure, but Ohio has ~4200 bars[0]. Which is roughly 1/4 the ratio of bars to people. [0]: https://rentechdigital.com/smartscraper/business-report-deta...

I don't think bars in Korea have parking minimums like they do in Ohio.

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

#54

Post by amscanne » Thu, Apr 24, 2025, 6:49 AM UTC

moralestapia wrote: post #48

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.

[flagged]

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.

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

#55

Post by [deleted] » Thu, Apr 24, 2025, 6:53 AM UTC

modeless wrote: post #5

srcreigh wrote: post #3

Title is incorrect. 178 days is the walking time of the optimal tour, not how long it took to solve for the best route

3 months, using 44 CPU-years, is that time.

[deleted]

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

#56

Post by amscanne » Thu, Apr 24, 2025, 6:57 AM UTC

Animats wrote: post #52

If you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result? The classic TSP approach is: 1. Hook up all the nodes in some arbitrary path. 2. Cut the path in two places to create three pieces. 3. Rearrange those three pieces in the six possible ways and keep the shortest. 4. Iterate steps 2-3 until no improvement has been observed for a while. This is not guaranteed to be optima…

Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html), the achievement here and all the computation is to establish that this is the lower bound (assuming I understood correctly).

So, the heuristic solver worked pretty darn well :) Although, I’m not sure how close it would have been the heuristic algorithm you are describing (I suspect that it is considerably more advanced for good reasons, randomly picking will take too long to converge).

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

#57

Post by moralestapia » Thu, Apr 24, 2025, 7:00 AM UTC

amscanne wrote: post #54

moralestapia wrote: post #48

Earlier quoted context omitted.

[flagged]

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,…

[flagged]

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

#58

Post by throwaway290 » Thu, Apr 24, 2025, 7:02 AM UTC

codemac wrote: post #45

lifthrasiir wrote: post #16

Earlier quoted context omitted.

That country has a population of 52 million, i.e. about 5 times Ohio.

Sure, but Ohio has ~4200 bars[0]. Which is roughly 1/4 the ratio of bars to people. [0]: https://rentechdigital.com/smartscraper/business-report-deta...

82k places in Korea include any restaurant or joint or karaoke with a license to serve alcohol. Personally I would not care to call 80% of them "bar".

So in Ohio probably everything with class C and D license. How many is not public but probably many times more than 4k.

Many actual street level bona fide bars in Seoul (which has half of all the people of the entire country and the most bars by far) are tiny rooms that fit a few people each. But you always have a "bar street" with 50 of those next to each other.

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

#59

Post by bigbacaloa » Thu, Apr 24, 2025, 7:02 AM UTC

notesinthefield wrote: post #8

I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.

"Bar" doesn't mean the same thing in every country. In Spain although a bar serves alcohol of all kinds it is also where one eats breakfast and lunch and gets a coffee. They are indispensable social centers and even a tiny town of 150 has one.

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

#60

Post by moralestapia » Thu, Apr 24, 2025, 7:06 AM UTC

alexchamberlain wrote: post #50

inasio wrote: post #32

Earlier quoted context omitted.

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.

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.