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
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!
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.
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.
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.
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.
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".
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.
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
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.
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.
- 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."
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.
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).
[0] https://en.m.wikipedia.org/wiki/2-opt
[1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...
LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/
Author's presentation about it
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)
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
[1] https://www.ibisworld.com/us/industry/ohio/bars-nightclubs/1...
[0]: https://rentechdigital.com/smartscraper/business-report-deta...
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.
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.
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.
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
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.
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.
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?
[1]: https://en.wikipedia.org/wiki/Designated_driver
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.
Plus being able to walk or take a train home makes them far more accessible for people than needing to drive home.
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.
South Korea apparently ranks #97 on alcohol deaths, so it's apparently not a problematic number of bars, by global standards.
https://www.math.uwaterloo.ca/tsp/korea/data/korea81998.xy.t...
I checked a few dots near where I live and they're all fried chicken joints. Yeah, we do love chimaek around here. :)
God I miss this place so much <3
How in the hell?
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.
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.
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.
[1] https://www.math.uwaterloo.ca/tsp/korea/computation.html
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.
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.
Post proof.
Is anything supposed to happen if you click on those red circles? I was hoping it will show name or other info!
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.
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.
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.
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.
>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.