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?
I think your astronomy skills are correct, but if we have to worry about actual travel then you would also have to consider things like fuel capacity, refuel opportunities, the fact that you probably don't want to actually fly through a star but around it, etc.
I think it's still valid to have a distinction between travel logistics and having a route that's at least theoretically possible. I suppose what they've calculated would work with a star gate like system, but then I'm not sure what the point of having minimal distance would be.
Isn't the flying around problem just "e" since it is so many orders of magnitude less than the distance between stars that for this calculation it is irrelevant anyway?
That's not true. The tour is 16.2 billion light years long, so even at the speed of light, it would take more than the current age of the universe to travel. Stars will move a lot over that period of time.
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).
The algorithm that OP describes is more commonly known as 2-opt [0]. The heuristic used in this case is referred to as LKH which I assume means the Lin-Kernighan Heuristic [1]. The latter is sort of a meta generalisation of the former.
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
LK heuristic is a bit more involved, but focuses on continuing to reverse the subarray on the [b, ..., d] segment, with search and backtracking involved. (I think that's refered to as sequential k-opt moves, but I think it's already quite hard to know what exactly LK is, and LKH does much more)
By focusing on the subarray, assuming distance symmetry (length from b to e is same as length from e to b, but there are correct workarounds if this does not hold), you can evaluate the cost of the new route in constant time (but with bigger k there's more moves to evaluate https://oeis.org/A001171)
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.
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
As someone married to a Korean, I am not surprised in the least. Every single one I have met (males at least) drinks like a fish. It is impossible to describe to a westerner just how ingrained the drinking culture is over there.
They are such an urban phenomenon. A largely empty rural state, with the legacy of prohibition, where you have to drive? That's going to have way fewer drinking locations. A culture of hanging out and drinking requires walkable urbanism. Many of the UK pubs pre-date the invention of the car; "peak pub" appears to have been the late 1800s with over 100,000.
I'm impressed that Korea has more than the UK, but this is definitely going to be a matter of size and the tiny Korean bars.
> A culture of hanging out and drinking requires walkable urbanism.
I don't think that's really true. In the UK, villages had pubs. Gradually some of the villages were joined together into larger cities, and the pubs remained. It wasn't planned as walkable urbanism.
You didn't have to plan to get walkable urbanism before cars. It just happened because everyone needed a pub, store, school, etc. within walking distance.
Codes like these are the secret sauce of America's asphalt deserts, in which you'll find - by international standards - comparatively large restaurants and stores. Walkable cities tend to gravitate towards smaller equivalents, and more of them.
A minimum amount of parking spots per patron capacity. So a bar with 60 people capacity must have 15 parking spaces. [0]
Usually parking minimums are WAY too high in required parking spaces to make sense in most cases. Which leads to stuff like a arena having 5x the land area be parking than what is taken up by the arena itself. [1]
>Usually parking minimums are WAY too high in required parking spaces to make sense in most cases.
That hasn't been my experience. Anytime I've wanted to go somewhere halfway popular the lot is usually full or nearly full. On the flipside, the lots are often empty during times when the business is closed, but reducing the size of the lot would exacerbate the issue of not being able to park nearby when the business is open. You aren't going to stop the US from being car centric, so you either have to dictate that businesses maintain a reasonable amount of parking or you have to have the municipality maintain several large parking structures throughout the city. Most cities would rather have the businesses that need the parking pay for the parking and most people would rather park near the businesses that they frequent.
> You aren't going to stop the US from being car centric
I think this isn't true. The same way suburbia spread out from cities, I think walkability can spread outwards too in baby steps.
For example, SF is relatively walkable/has public transit. The next step would be slowly removing parking minimums and making the areas surrounding SF more walkable. And then over time as people in those surrounding areas start using their cars less (not getting rid of them but at least trying to do short journeys on foot/bike/transit).
Over time that spreads outwards because half the community served by an area no longer needs a car for their daily travel and the envelope of walkability spreads further.
Sure you can slowly, over a long time, convert already dense areas into being less car centric, but you aren't going to make the rest of the country that way. Parking minimums, when they exist, are set by super local governments, they already don't exist or are set very low in areas of high density. The solution is to increase density, but again you aren't going to do that in the rest of the country. Random bars in Ohio are still going to have large parking lots, because land is cheap and given the choice, most people prefer less density.
The idea of a bar (ie a place people go to get drunk) with a dedicated parking lot strikes me as particularly bad for road safety. I'm baffled that this is not only encouraged, but mandated.
How do people do this in practice? Just drink and drive and hope they don't crash / get fined? Or does everybody bring 1 friend who sips colas the whole night?
Yeah but I mean, if everybody goes to the pub by car, does it mean everybody brings a designated driver? Or is this one of those things where everybody drives drunk but pretends nobody does?
Mostly the latter IMO. The most popular bar where I grew up is on a busy highway with no housing within walking distance. Parking lot reliably fills up every weekend night, mostly with single occupancy vehicles. You can do the math.
It's pretty common for people drive to the bar, get drunk, taxi/Uber/Lyft/DD home, and then return the following day to get their vehicle. I don't think it makes sense personally, but I also don't drink at all so I'm not a great judge here.
Parking lots are not mandated for bars in the US, at least not everywhere. I helped my girlfriend's dad open a bar in Long Beach 20 years ago. The city required us to pay for the maintenance of three streetside parking spaces, but that was it. Pay the city. We didn't have to build anything that didn't already exist.
>Parking lots are not mandated for bars in the US, at least not everywhere.
This, they are making the mistake that all the people on /r/askamerican do over on reddit. Laws like this mostly aren't nationwide or even statewide, they are decided on a very local level.
This is also upper-bounded by the law; Ohio only issues one class D-5 liquor license (license to sell beer, wine, and spirits) per 2000 residents, which roughly maxes it out at ~5950 bars (in practice this looks to be rounded up on a per-town basis, making this an underestimate). An Ohio with the population of South Korea would only be allowed ~25000 bars.
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.
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!
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. :)
Many countries have much more used “public” spaces, and people spend much more time in them, together.
The idea of driving home to the suburbs and locking yourself into your private home is very North American.
I just got back from10 months across Europe. The number of people in public places eating, chatting and just spending time (no simply going somewhere) makes LA or Chicago look like a ghost town.
After living there for about four years, my mind goes immediately to soju. Not sure if there is a connection, but that’s something I might deep dive with an LLM today.
"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.
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".
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...
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.
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.
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/.
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.
It's always worth spending 30s verifying something like this by reversing what you're arguing - in this case, 5000 * 365 * 40 is obviously more than 82,000.
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
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
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.
There was a man who documented his travel to every country in the world. Not long before he was finished, South Sudan gained independence and he had to take a special trip there to complete his journey, which apparently had already completed all the other countries in Africa long 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.
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.
>But you can just run the bounding algorithms yourself, or prove they are incorrect.
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 x2.
The proof here is essentially the execution log of the bounding program. I imagine that this would be TB, PB or beyond. Not every proof is some clever paper, some are just brute force. Like proving a number is prime, or calculating the Nth digit of Pi. A paper doesn’t always make sense, but you can still announce what you’ve done (and maybe you get a paper with algorithmic details, but it’s not a proof for specific the instance).
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.
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
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.
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."
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?
I think your astronomy skills are correct, but if we have to worry about actual travel then you would also have to consider things like fuel capacity, refuel opportunities, the fact that you probably don't want to actually fly through a star but around it, etc.
I think it's still valid to have a distinction between travel logistics and having a route that's at least theoretically possible. I suppose what they've calculated would work with a star gate like system, but then I'm not sure what the point of having minimal distance would be.
The bar problem has its own issues. With that many bars some may close or new ones may appear during the time of the walk.
Isn't the flying around problem just "e" since it is so many orders of magnitude less than the distance between stars that for this calculation it is irrelevant anyway?
At that point we should also factor in time relativity, making it hard to measure the actual location of the stars at all.
This also doesn't handle new bars being opened and closed as you travel. Not to mention bouncers having bad days so you will have to revisit the bar.
I don't think this is presented as a means to get drunk around south korea. It's just an interesting application of TSP
But they are so far apart and move on roughly the same trajectory that it shouldn't really matter.
That's not true. The tour is 16.2 billion light years long, so even at the speed of light, it would take more than the current age of the universe to travel. Stars will move a lot over that period of time.
Yes I was assuming instant travel, even with one star the trajectory will be nonlinear.
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.
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).
The algorithm that OP describes is more commonly known as 2-opt [0]. The heuristic used in this case is referred to as LKH which I assume means the Lin-Kernighan Heuristic [1]. The latter is sort of a meta generalisation of the former.
[0] https://en.m.wikipedia.org/wiki/2-opt
[1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...
2-opt is a bit simpler.
LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/
https://www.youtube.com/watch?v=tChnXG6ulyE
Author's presentation about it
Iirc the (probably simplified) LKH heuristic they used:
n is a small number like 4 maybe 5?2-opt: [a, b, ..., d, e]
reversing subarray from b to d is a 2-opt move.
3-opt (1 particular move):
a b c d e f
a e d c b f -- reversal from b to e
a e d b c f -- reversal from c to b
LK heuristic is a bit more involved, but focuses on continuing to reverse the subarray on the [b, ..., d] segment, with search and backtracking involved. (I think that's refered to as sequential k-opt moves, but I think it's already quite hard to know what exactly LK is, and LKH does much more)
By focusing on the subarray, assuming distance symmetry (length from b to e is same as length from e to b, but there are correct workarounds if this does not hold), you can evaluate the cost of the new route in constant time (but with bigger k there's more moves to evaluate https://oeis.org/A001171)
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.
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
I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.
americans always compare massive cities to empty states
South Korea has 5x the population of Ohio, but around 27x the number of bars [1]. So it really is a lot of bars.
[1] https://www.ibisworld.com/us/industry/ohio/bars-nightclubs/1...
As someone married to a Korean, I am not surprised in the least. Every single one I have met (males at least) drinks like a fish. It is impossible to describe to a westerner just how ingrained the drinking culture is over there.
They drink more than Eastern and Northern Europeans. It's insane!
Snark aside - I used this site which compares the country question to the location closest to you. I live in ohio. https://www.mylifeelsewhere.com/country-size-comparison/unit...
Empty lol
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...
Just to compare, they also have a tour for the UK https://www.math.uwaterloo.ca/tsp/uk/index.html : 49,687 pubs.
They are such an urban phenomenon. A largely empty rural state, with the legacy of prohibition, where you have to drive? That's going to have way fewer drinking locations. A culture of hanging out and drinking requires walkable urbanism. Many of the UK pubs pre-date the invention of the car; "peak pub" appears to have been the late 1800s with over 100,000.
I'm impressed that Korea has more than the UK, but this is definitely going to be a matter of size and the tiny Korean bars.
> A culture of hanging out and drinking requires walkable urbanism.
I don't think that's really true. In the UK, villages had pubs. Gradually some of the villages were joined together into larger cities, and the pubs remained. It wasn't planned as walkable urbanism.
You didn't have to plan to get walkable urbanism before cars. It just happened because everyone needed a pub, store, school, etc. within walking distance.
But it wasn't urban. That's my point.
I don't think bars in Korea have parking minimums like they do in Ohio.
What's a parking minimum?
The minimum number of parking that needs to be available per seat/dining area.
https://codelibrary.amlegal.com/codes/plaincity/latest/plain...
Codes like these are the secret sauce of America's asphalt deserts, in which you'll find - by international standards - comparatively large restaurants and stores. Walkable cities tend to gravitate towards smaller equivalents, and more of them.
A minimum amount of parking spots per patron capacity. So a bar with 60 people capacity must have 15 parking spaces. [0]
Usually parking minimums are WAY too high in required parking spaces to make sense in most cases. Which leads to stuff like a arena having 5x the land area be parking than what is taken up by the arena itself. [1]
0: https://codelibrary.amlegal.com/codes/harrison/latest/harris... (this is for harrison, ohio, just happened to be the first result I found. it's under commercial -> "Tavern, bar, club, lodge, and dance hall.")
1: https://www.youtube.com/watch?v=OUNXFHpUhu8
>Usually parking minimums are WAY too high in required parking spaces to make sense in most cases.
That hasn't been my experience. Anytime I've wanted to go somewhere halfway popular the lot is usually full or nearly full. On the flipside, the lots are often empty during times when the business is closed, but reducing the size of the lot would exacerbate the issue of not being able to park nearby when the business is open. You aren't going to stop the US from being car centric, so you either have to dictate that businesses maintain a reasonable amount of parking or you have to have the municipality maintain several large parking structures throughout the city. Most cities would rather have the businesses that need the parking pay for the parking and most people would rather park near the businesses that they frequent.
> You aren't going to stop the US from being car centric
I think this isn't true. The same way suburbia spread out from cities, I think walkability can spread outwards too in baby steps.
For example, SF is relatively walkable/has public transit. The next step would be slowly removing parking minimums and making the areas surrounding SF more walkable. And then over time as people in those surrounding areas start using their cars less (not getting rid of them but at least trying to do short journeys on foot/bike/transit).
Over time that spreads outwards because half the community served by an area no longer needs a car for their daily travel and the envelope of walkability spreads further.
Sure you can slowly, over a long time, convert already dense areas into being less car centric, but you aren't going to make the rest of the country that way. Parking minimums, when they exist, are set by super local governments, they already don't exist or are set very low in areas of high density. The solution is to increase density, but again you aren't going to do that in the rest of the country. Random bars in Ohio are still going to have large parking lots, because land is cheap and given the choice, most people prefer less density.
The idea of a bar (ie a place people go to get drunk) with a dedicated parking lot strikes me as particularly bad for road safety. I'm baffled that this is not only encouraged, but mandated.
How do people do this in practice? Just drink and drive and hope they don't crash / get fined? Or does everybody bring 1 friend who sips colas the whole night?
We call the latter a designated driver [1] though as you can imagine sometimes the designated driver is "only" slightly drunk.
[1]: https://en.wikipedia.org/wiki/Designated_driver
Yeah but I mean, if everybody goes to the pub by car, does it mean everybody brings a designated driver? Or is this one of those things where everybody drives drunk but pretends nobody does?
Mostly the latter IMO. The most popular bar where I grew up is on a busy highway with no housing within walking distance. Parking lot reliably fills up every weekend night, mostly with single occupancy vehicles. You can do the math.
Taxis exist.
The parking minimum is for taxis?
It's pretty common for people drive to the bar, get drunk, taxi/Uber/Lyft/DD home, and then return the following day to get their vehicle. I don't think it makes sense personally, but I also don't drink at all so I'm not a great judge here.
Parking lots are not mandated for bars in the US, at least not everywhere. I helped my girlfriend's dad open a bar in Long Beach 20 years ago. The city required us to pay for the maintenance of three streetside parking spaces, but that was it. Pay the city. We didn't have to build anything that didn't already exist.
>Parking lots are not mandated for bars in the US, at least not everywhere.
This, they are making the mistake that all the people on /r/askamerican do over on reddit. Laws like this mostly aren't nationwide or even statewide, they are decided on a very local level.
A lot of bars in walkable cities fit about 10 or fewer people. East Asia in particular has loads of tiny bars.
Plus being able to walk or take a train home makes them far more accessible for people than needing to drive home.
This is also upper-bounded by the law; Ohio only issues one class D-5 liquor license (license to sell beer, wine, and spirits) per 2000 residents, which roughly maxes it out at ~5950 bars (in practice this looks to be rounded up on a per-town basis, making this an underestimate). An Ohio with the population of South Korea would only be allowed ~25000 bars.
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.
Ok, that gets the numbers in line -- there are about 27,000 liquor licenses in Ohio, according to a random Google, which is about the same per capita.
South Korea apparently ranks #97 on alcohol deaths, so it's apparently not a problematic number of bars, by global standards.
Ohioans love "big bars".
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
I checked a few and there's a lot of restaurants included.
https://www.math.uwaterloo.ca/tsp/korea/data/korea81998.xy.t...
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. :)
In korea after a certain hour every restaurant, karaoke, PCBang, and hotteok parlor is basically a bar :)
God I miss this place so much <3
NYC that is like 20 miles across has 11,000 locations that serve alcohol.
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?
Many countries have much more used “public” spaces, and people spend much more time in them, together.
The idea of driving home to the suburbs and locking yourself into your private home is very North American.
I just got back from10 months across Europe. The number of people in public places eating, chatting and just spending time (no simply going somewhere) makes LA or Chicago look like a ghost town.
Sure, but that's still an astronomically higher number of bars
the UK in totality has 45k pubs, nearly half Seoul's number
this is mostly emblematic of South Korea's major alcoholism problem. way too many bars and too much drinking.
The bars may be much smaller.
South Korea really said "you will not be thirsty on our watch."
How many bars do you expect are in Ohio?
Less than 40,000
One would hope with 5x fewer people!
I think it’s far fewer, probably under 5,000 if we are really talking about “bars” and not any ole liquor licensed establishment such as a restaurant…
It seems like you're pretty close with that guess.
https://www.ibisworld.com/us/industry/ohio/bars-nightclubs/1... (2025) estimates there are about 3,000 "bars and nightclubs" in Ohio.
And https://vinepair.com/articles/map-states-with-most-bars/ (2022) estimates there are 1800 bars in Ohio, apparently placing it in the Top 10 of states with the most bars.
And South Korea has one of the highest rates of stomach cancer.
After living there for about four years, my mind goes immediately to soju. Not sure if there is a connection, but that’s something I might deep dive with an LLM today.
To be fair, it does sound like a pretty tough place to stomach.
"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.
Town? More like village. You can have a nearly empty church, but there's no village without a bar.
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".
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....
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
Gotta respect the planning that went into choosing a problem that's both absurd and actually solvable
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
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.
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.
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/.
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.
Yeah, I probably mixed it up with the Hamiltonian Path problem. It was a long time ago
>80k with proof
Post proof.
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.
OSRM lead dev here. Love to see this large of an instance being solved.
Oh no, looks like a few new bars opened up, and a few others closed. Time to recalculate.
If you spent 40 years of your life on this path, you would still be visiting 5.616 bars per day. Nuts.
Less than 6 bars a day is pretty doable! :-p
Isn't comma the decimal separator ;)
It depends on which part of the world you live in.
It's always worth spending 30s verifying something like this by reversing what you're arguing - in this case, 5000 * 365 * 40 is obviously more than 82,000.
It’s not that many bars.
That’s also not considering whether they’re open or existing anymore after so much time has passed.
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
Has anyone done the opposite of this, finding the longest possible route?
Seem i do need a pair of dry socks for part of the walk.
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
Does it put the order of others off,i.e. a net loss?
Where?
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.
Sadly I'm not a Soju fan
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.
Very interesting..
Is anything supposed to happen if you click on those red circles? I was hoping it will show name or other info!
It would suck to get to bar 51,248 only to find out it's now permanently closed
There was a man who documented his travel to every country in the world. Not long before he was finished, South Sudan gained independence and he had to take a special trip there to complete his journey, which apparently had already completed all the other countries in Africa long ago.
Does it account for "pit stops"
They call it the Traveling Salesman Problem, but it sounds more like the Drunkard’s Walk to me.
I’d like to call it a stumble :)
impresive, I have forgot TSP after graduated.
“The locations were downloaded from a database maintained by the Korean National Police Agency.”
Is that one of the problem quantum computers would resolve instantly if it is actually possible to scale them up?
traveling drinking man's problem
No it's: The traveling ale-man's problem. ;)
Kids, we're going on a road trip!
>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.
>What are you actually expecting here?
Didn't you read my comment?
A proof.
Why?
Because they claim to have one.
How?
A link to a paper or something.
Come in, this stuff is very low level.
>But you can just run the bounding algorithms yourself, or prove they are incorrect.
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 x2.
The proof here is essentially the execution log of the bounding program. I imagine that this would be TB, PB or beyond. Not every proof is some clever paper, some are just brute force. Like proving a number is prime, or calculating the Nth digit of Pi. A paper doesn’t always make sense, but you can still announce what you’ve done (and maybe you get a paper with algorithmic details, but it’s not a proof for specific the instance).
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?
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
(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 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.
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.
(Submitted title was "Shortest walking tour to 81,998 bars in Korea — TSP solved in 178 days".)
[dead]