Computer Scientists Break Traveling Salesperson Record
quantamagazine.org
quantamagazine.org
...
> “This is a result I have wanted all my career,” said David Williamson of Cornell University, who has been studying the traveling salesperson problem since the 1980s
I love this. Oh to be a theoretician.
Here's hoping for a flood of further improvements.
In a limited-enough space (like an event), this works out just fine. I'm glad I'm not the guy who needs to solve GoogleMap's routing problems though. I wonder if they have a huge BigTable store of every street intersection pair on the planet and a recalculated best route between them? I _hope_ they do something smarter than my "works in my constrained requirements space" brute-force hack...
The hard part for real-world directions is getting the cost-function right. Older map systems used to make some very questionable assumptions that made them quite inaccurate (one example; assume all highway miles are equal; some were 55MPH and have traffic lights, railroad crossings and stop-signs others were 65 with no at-grade intersections -- today even higher speed limits are seen as the lingering effects of the national speed-limit have worn off).
Even after 1995, many states were very slow to raise the speed limit (I lived near the Maryland/Virginia boarder and remember Maryland did well before Virginia), and when they did raise the speed limit it was by small amounts.
Today, you can drive from Los Angeles to New York and not hit any significant stretches of freeway with speedlimits under 65, and west of the Mississipi river, you will spend most of it at 70mph or higher.
On top of that, the actual speed that will get you pulled over can be much higher (In CA you are very unlikely to get pulled over for single-digit MPH speeding on a freeway, making a 65 speed limit a de-facto 74; in the northeast US it's not uncommon to get pulled over for going just 5MPH over the posted limit).
Edit: to add value to the conversation: in germany I find googles estimates on long car trips quite accurate. And I'm actually a very erratic driver, sometimes taking every hole in traffic I can to get ahead, just slowing down to speed limit+20km/h where there is a speed trap, sometimes just cruising 80km/h on open autobahn getting overtaken by cargo trucks
FWIW, Advisory speed-limits on autobahn are similar to the western US statutory speed limits (130km/h == 80mi/h). That being said, 200km/h and no other moving violations would quite possibly get you thrown in jail in "The land of the free"
The NMSL (National Maximum Speed Limit) was enacted in 1973, modified in 1987 to allow 65 mph speed limits on rural interstates, and repealed in 1995.
Many states in the southeast, midwest and west raised their posted speed limits very soon after the NMSL was repealed. States in the northeast took a bit longer to update their laws to remove their state maximum speed limit.
An example: https://maps.app.goo.gl/HhMWPgE2gznsPsQ9A
Unfortunately IIRC most of the screenshots I took show my actual address/immediate surrounding area etc, so they'd be fairly heavily censored. If anyone [is actually reading this and] is especially interested, I can try braving my scary not-organized screenshot archive and try and find them.
I don’t think waterfall is necessarily bad, that agile is always right, or that there aren’t other good practices. But practicing waterfall and calling it “agile” is rarely going to end well for anyone.
https://pragtob.wordpress.com/2012/03/02/why-waterfall-was-a...
And to be very honest. It doesn't work if the people in the team don't think Agile. Your team needs to be able to self-reflect and try to improve themselves just as they'll do with client work in a sprint.
You cannot appoint somebody to the strange title of “scrum master” (which I guess makes the rest of us scrum slaves?) to lead a process of “daily scrum” where we look together at a kanban board and make sure that we are “sprinting” and then turn around to insist that you value “individuals and interactions over processes and tools,” which is ¼ of the Manifesto. You have voted with your intention and your vote was to value your process and tools over trusting the individual developers and letting them have direct interactions with your customers.
Even the word “sprint.” I used to play Ultimate in one of the teams in the Dutch national league, it is a sprinting sport. The word “sprint” means exhaustion. It means stopping. If you jog around in Ultimate you lose, you have to rest, sprint, rest, sprint. If your model is “always sprinting” then do not tell me that you value “individuals and interactions.” And if you do value the latter please either (a) remove the metaphor “sprint” from your process or (b) add “rest weeks” after each sprint to “clean up” the mess you made! Anything else is lying to yourself.
The phenomenon of estimating “story points” is even worse, no? It is intrinsically about processes and tools and the idea of a developer having a phone call or face-to-face with the client directly to see if this feature request is actually accurate, deciding that it is not, and trashing it to open a different request... it's not just “do we claim those juicy story points when this happens?” but also “was part of your measure of ‘complexity’ the complexity of determining that the Ask did not meet the Need?” ...And so the fundamental idea of estimating a “todo” does not fit well with agile, whereas you can estimate “in progs” and “done” just fine.
And before you say “no by the time we estimate we should already know that we want the feature, devs should never have to talk to clients,” please be aware that this response explicitly abdicates another ½ of the Agile manifesto, “customer collaboration over contract negotiation” and “responding to change over following a plan.” The whole point of the Agile manifesto is that your kanban board is stale. Not because it's a kanban board, but because it is written down. Like one of the four principles (the last ¼ not covered in the above ¾) is explicitly anti-literary.
This is sort of “no true Scotsman” of me but my read is that the moment Agile was systematized, it died a little on the inside. It was a “screw your systems!” reaction that then got steamrollered by the real world, where “bullshit jobs” and middle management reign even though they bespeak a bureaucratic feudalism rather than a lean-and-mean capitalism.
What I am challenging in the above is that there is a "lip service" given rather than a deep assimilation. So when the principles say "business people and developers must work together daily throughout the project" they mean that there should be an open-door policy, “hey Amanda I am working on the Estimating-Work-in-Process application and I was wondering what you do with ____” “Oh, that is not supposed to be possible,” type of interactions. The ‘lip service’ is “your boss will answer any questions at daily stand-up.”
Because these interactions are routine, the idea of needing constant scheduling and progress updates ideally ‘should be’ a lesser issue. People want progress updates to make sure that you are not spending all your time on Reddit, they will be able to see that more readily if they see you working.
The core of agile is anti-establishment thinking. One of the principles is “The best architectures, requirements, and designs emerge from self-organizing teams. At regular intervals, the team reflects on how to become more effective, then tunes and adjusts its behavior accordingly.” Elsewhere Don Wells elaborates on it, “Don't panic. With professional software engineers on our project we can relax knowing that the team will do what is needed to get the job done. Any activity needed with any combination of people will just get done without any further scheduling or ceremony. This is the spirit and benefit of a self organizing team.”
And so a fundamental idea of agile, perversely enough, is that you’re not going to have one size fits all, there is no one ‘proper implementation.’ There is just the way that you made it work. If you have different personalities it’s gonna express differently.
I am not being facetious here, though I realize it sounds kind of like it! Adam Savage had a great video a little while back about something unrelated—weathering prop money—where he took live questions from the audience, and one question was about “the best way” to make that money look bloody, and he answered in true artisan style:
> So, your question though, “what is the best way”... The answer is, there is no, there is no best way! There is the way you figure out how to do it. Yeah! That’s really the thing. It may be that you’ve gotta, like, take a brush and kinda work at a whole bunch of different bills, and then take the stack and then effect the stack, right?, I think that’s like a multi-stage process, and then you should do some tests with different paints and see, like, under the lighting conditions these will be seen—I don’t know if it’s for a theater or a film—does it communicate? Does it tell you that it’s bloody, dirty money? That’s the question to be asking, you gotta hold it up, look at it, [mimes looking at it and pausing and thinking] “does that sell to me?”—and ask other people, “does this sell?”... and like most of the time they’re gonna go, “no,” and you’re gonna keep on going. But it’s trial and error.
And like the fundamental story about agile is that agile is trial and error, it is about trying to work together as a team and being like “did that work” and the answer is usually “no, Leah is totally burned out after she had to work 60+ hours of straight development that one week,” or “Alvin is having trouble with nobody inviting him in, he wants to start contributing to this project and everybody is like ‘nah man we got it’ and he is being excluded” and you’re gonna have to reshape. There is a necessary aspect of vulnerability in other words in any proper development strategy whether top-down design-first waterfall or agile or something else.
There is no one agile software development process. There is a set of agile software development values. It is a values-driven approach, “how are we living up to our self-commitments today?” rather than “did I follow the appropriate procedure?” And thus it is quite anarchist at its fundamental core. This is probably why I am ragging on scrum in the end, scrum came in and said “there is a non-anarchist way to do agile” and I am sitting here like “uh, do you know what you just said?”
With that said, all the usual caveats, I understand that you want to be able to state what all is likely to be in an upcoming release and what all isn’t and this requires creating estimates and so forth. But perhaps the most damning thing is when estimates turn into deadlines. When an estimate becomes a deadline it gets padded and re-padded, then the urgency of the feature gets de-emphasized because you have such an abundance of time to do it in, so you spend a bunch of time up-front completing your “design doc” about what you are about to build and then someone asks to weigh in and “approve it” and you have reinvented waterfall.
I've only seen scrum implemented as a planning tool. But the teams aren't truly agile.
> And like the fundamental story about agile is that agile is trial and error, it is about trying to work together as a team and being like “did that work”
This is exactly what I meant with needing the team to be able to self-improve based on experiences. You can trial-and-error velocities all you want. But if you don't employ that same agility on a deeper level it's never going to work anyway.
I kinda feel all the _actual_ innovation is doing things that align with Agile's underlying principals of valuing individuals/working-software/response-to-changes over processes/documentation/plans - while all th3e people who _talk_ about doing "Agile" rarely follow those principals, and mostly just mean "We have meetings we call 'standups', and negotiated deadlines that we call 'sprints'".
Please don't take quotes out of context
This wasn't intended to be read as sarcastic. It really is a great development. It's still amusing that the number is so tiny.
Simulated annealing was inspired by thermodynamic free energy involved in crystal formation from annealing metal. [1]
I combined it with a Breath of the Wild waypoint generator [2] to make my way around the map [3] in a mostly optimal fashion for my trip about Hyrule.
If you ever have a toy problem or even a real one, I suggest experimenting with pytspsa to see and understand in a concrete way the problem is solved.
[0] https://github.com/ildoonet/simulated-annealing-for-tsp
[1] https://en.wikipedia.org/wiki/Simulated_annealing
[2] https://github.com/MrCheeze/botw-waypoint-map
[3] https://user-images.githubusercontent.com/2829875/28661246-0...
I had good results with genetic algorithms as well.
I guess later in the game one doesn't mind randomly walking right by the castle just because it is the shortest path, just going to eat some time dealing with each guardian of course.
Same for swimming across a the river twice around a bend rather than just following the coastline.
Also there are 226 waypoints, the linked map is missing a lot...
I am not sure what it is trying to show. Was this the waypoints you had not done at the end of the game?
Anyway, the grandparent solves the Euclidean TSP which is still an NP-complete problem. I will be reluctant to say that it is an easier problem in a general sense. I agree though that there are better and easier approximations for it.
That is 0.0000000000000000000000000000000002% better than the existing solution.
Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?
https://www.intel.com/content/www/us/en/products/docs/proces...
It does mention choosing tree paths at random... so couldn't that be an improvement by chance?
It's lengthy and full of some quite technical sections, but those are interspersed with sections sketching the high-level intuition and proving more informal versions of the technical theorems in simplified cases. An example is on p. 19, section 3.1, "Ideas underlying proof of Theorem 3.1".
I think this is the paper? https://arxiv.org/abs/2007.01409
> they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.
That’s so subtle to suggest but incredible hard to prove
Isn't that really the best we can hope for? It's an NP-complete problem, but we can still realistically hope that researchers might discover efficient algorithms for solving subsets of the problem space, hopefully broad subsets.
If we get to the point that 90% of travelling salesman problems can be solved quickly, and the remaining 10% can quickly be approximately solved (to within 5% percent of the optimum solution, say), that would be pretty great, even if we never 'really' crack NP-complete problems. (Which, of course, might not even be possible.)
As an example, a smart TSP algorithm should be able to very quickly solve problems where all nodes fall on points in a circle.
(Disclaimer: this stuff isn't my wheelhouse, corrections welcome.)
Finding the optimal solution is NP-complete, but approximations are not necessarily so:
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co...
The TSP problem is NP-complete, but it may be possible to come up with an 'incomplete' algorithm that works efficiently for a large subset of the problem space, and it may be possible to find an approximate algorithm that efficiently finds guaranteed near-optimum solutions to all problems.
Neither of those two things requires doing the truly difficult (perhaps impossible) work of coming up with a precise, complete, and efficient algorithm to an NP-complete problem.
circuit satisfiability and related hard problems are all reducible to each other
From the paper you linked:
heuristics based solutions are still superior to deep learning based solvers regarding accuracy and execution time for larger problem sizes.
For example, given a list of cities, an approximate solution on actual roads to visit all of them once?
Someone should make a front end for this.
https://en.wikipedia.org/wiki/Talk:Travelling_salesman_probl...
Older than you’d think.