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

[gku]

If you find this impressive, take a look at the 1.33 billion stars TSP solution provided by the same authors.

- Gaia DR2 (1,331,906,450 Stars): https://www.math.uwaterloo.ca/tsp/star/gaia2.html

> "The tour is at most 1.0038 times the length of a shortest-possible route."

[gampleman]

But that presumably doesn't handle the relative motion of the stars, which makes the problem even trickier, since the distances will change as you travel, no? Or is my astronomy off base here?

[bscphil]

Unfortunate - they didn't pin the version of Three.js they were using for the interactive viewer at https://www.math.uwaterloo.ca/tsp/star/star10m_tour.html

And as a result it's been broken since May 2022: https://github.com/mrdoob/three.js/releases/tag/r141

I downloaded the HTML file and replaced the link with a versioned one, and the viewer still works just fine.

[Animats]

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.

[amscanne]

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).

[neves]

https://www.youtube.com/watch?v=tChnXG6ulyE

Author's presentation about it

[yobbo]

Iirc the (probably simplified) LKH heuristic they used:

  For each iteration:
     apply some randomisation
     starting at each place
         cut the path in 2..n places
           reconnect in the most optimal way 
           if the new tour is the new best, save

n is a small number like 4 maybe 5?

[noduerme]

It's strange that they don't mention the total distance. I understand that the point-to-point travel time is what they're solving for, but it would be interesting to know what the actual distance of travel was, if for no other reason than calculating caloric burn. But then you could also see how much it deviated from the shortest-distance path.

[internetter]

Proper routing is also an expensive computation. Yes you could just run A* or something on the roads but that would assume no closures, no one way roads, wouldn’t account for elevation change, ect. Using a proper routing API is almost certainly cost prohibitive

[notesinthefield]

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

[kijin]

Looks like they got their hands on a dataset of every restaurant that is licensed to serve alcohol -- or at least a decent subset of such restaurants, filtered by menu or whatever.

I checked a few dots near where I live and they're all fried chicken joints. Yeah, we do love chimaek around here. :)

[bbno4]

americans always compare massive cities to empty states

[dyauspitr]

NYC that is like 20 miles across has 11,000 locations that serve alcohol.

[lifthrasiir]

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

[gniv]

I checked a few and there's a lot of restaurants included.

https://www.math.uwaterloo.ca/tsp/korea/data/korea81998.xy.t...

[jihadjihad]

What's really cool is if you go to a site like [0] that shows the "true" size of countries etc. (i.e. not distorted by a projection), Indiana is probably the most analogous state to South Korea, in terms of size and shape. But South Korea has 7x the population of Indiana!

Really puts into perspective a movie like "Train to Busan", which would be like taking a train from Gary to Madison!

0: https://thetruesize.com

[bobxmax]

If this is correct, it seems like Seoul has over 40x the number of bars that Chicago has, despite having only about 4x the population

How in the hell?

[BrtByte]

South Korea really said "you will not be thirsty on our watch."

[zeckalpha]

How many bars do you expect are in Ohio?

[ekianjo]

And South Korea has one of the highest rates of stomach cancer.

[bigbacaloa]

"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.

[OsrsNeedsf2P]

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

[BrtByte]

Gotta respect the planning that went into choosing a problem that's both absurd and actually solvable

[omoikane]

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

[bjornsing]

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

[tiernano]

reminds me of a question they used to ask in the Irish army back in the 60s. My Dad told me this. "How do you get from Bachelor's Walk to Collins Barracks without passing a bar?". People would spend hours and days working on the answer. In the end, the answer was "Go in to every one".

[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.

[eduardosalaz]

There is tons of work to do on running optimization algorithms in GPU. In its current form, Branch and Bound and Cutting Planes do not gain an advantage if implemented in CUDA. There is a new algorithm, PDLP, which is implementable in GPUs but it is still in early stages. For more, see https://blogs.nvidia.com/blog/cuopt-open-source/.

[JohnKemeny]

The thing is that Euclidean TSP needs a lot of data to encode hard instances.

N=15 was even considered solved in the 60s, and N=20 has never been considered large instances, especially not of Euclidean TSP.

I cannot see how anyone could say 13 is the max: you need 100k memory slots and 1M comparisons. This has been trivial for quite some time.

[moralestapia]

>80k with proof

Post proof.

[pugworthy]

During COVID I made it a goal to walk every street in my town using the web-based CityStrides (https://citystrides.com/) tracker. It keeps tracks of streets you have walked and lets you know what percentage of a town you have walked. It didn't optimize my routes for coverage, but it was a fun mental puzzle to plan out my walks to hit as many streets as possible without duplication. An automated tool might be fun, but doing it by hand was part of the journey as it were.

As you browse the CityStrides site you can find people's LifeMaps which show all their walking. Some people have done amazing amounts of walking. See this user for example and their coverage of Paris, France...

https://citystrides.com/users/15259/map#48.85741101618777,2....

[flerchin]

Oh no, looks like a few new bars opened up, and a few others closed. Time to recalculate.

[blt]

Branch-and-bound is an algorithm "from the book" to me. Fundamentally very simple, provided you view the LP solver as a black box, but incredibly useful.

[DennisL123]

OSRM lead dev here. Love to see this large of an instance being solved.

[mofunnyman]

If you spent 40 years of your life on this path, you would still be visiting 5.616 bars per day. Nuts.

[labster]

They call it the Traveling Salesman Problem, but it sounds more like the Drunkard’s Walk to me.

[The28thDuck]

I’d like to call it a stumble :)

[Catagris]

I looked at near my home, they missed a few. A issue is that in Korea a lot of the local spots are not on any public maps.

[HPsquared]

Has anyone done the opposite of this, finding the longest possible route?

[BrtByte]

This is both hilarious and genuinely impressive. A TSP solution involving nearly 82 000 bars? That's a level of dedication to both math and beer I didn't know I needed in my life

[bjornsing]

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.

[pkhuong]

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.

[z3t4]

I zoomed in on the map and discovered at least one shortcut where one could have saved a few seconds, now is that proof enough that the solution is not optimal? :P

[throwaway519]

Does it put the order of others off,i.e. a net loss?

[bk496]

Where?

[sylware]

Is that one of the problem quantum computers would resolve instantly if it is actually possible to scale them up?

[kopirgan]

Very interesting..

Is anything supposed to happen if you click on those red circles? I was hoping it will show name or other info!