I need to get back to just talking about mathematics problems some. Happily there was some news come across my desk. It’s about the Travelling Salesman Problem. This is one of those classic problems, simple to state and obviously interesting, and that are terribly hard to solve. How do you draw a path connecting a large number of points with the shortest total path? You can recast what you’re doing: make the path that takes the shortest time, or that has the lowest cost, the least energy, the greatest profit, whatever. Optimization problems are very alike, and useful.
There’s not many good answers to the problem, though. Basically, test out every possible combination and pick the best one from all that. For large enough problems this is hopeless. For small enough problems, though? You can work something out. So there’s this report of researchers, lead by Professor Takayuki Kawahara at the Tokyo University of Science. They’ve developed an integrated circuit with really good performance for, they believe, up to 22 ‘cities’. That 22 is a breakthrough tells you something of how hard the problems are.
I’m unclear, from the press release, just how the system works. (I’m also unsure, from reading the press releases, that they have actually used this for 22 cities or whether they have good reason to think it will work as hoped for. I may be over-parsing.) There’s a description of using “spin cells” and it happens I know about something named spin cells. And that they are used in optimization problems. What I do not know is that my spin cells are the spin cells being used here. If I find out, I’ll share.
nebusresearch 
arm in sling so lower case hmm sounds like a stage direction in death of a salesman the problem seems to have reminded me of poor old willy loman wonder if he had an optimisation answer
LikeLike
Not to worry, and you take good care of your arm there.
Willy Loman’s the thing everyone thinks of with the Traveling Salesman Problem. Better routes would probably have helped him, at least, spend less time in transit, or on travel costs. But a lot of optimization problems can be cast as some form of getting between sets of points, with some distance (cost, speed, whatever) the trouble of going between these points. And then tools to solve the traveling problem apply again.
LikeLiked by 1 person
ha reminds me of the curse of touring bands with bad management – pingponging from one side of the country to the other then back again
LikeLike
Oh, now, we can ask whether the worst-possible-case for a traveling salesman, the trip that takes the longest distance, is just as hard to calculate as the best-possible-case, that takes the shortest distance. I very much want to say that it’s just as hard to find the worst solution as the best. I’m not confident that it is, though, even if we impose restrictions like only visiting each city the one time. (If we can visit each city an unlimited number of times, obviously, you can just go back and forth between two cities until you’ve made the trip as long as you can stand.)
LikeLiked by 1 person
cannot see the worst solution attracting research funding tho i speak as a non-mathematician – in which incapacity i am somehow reminded of Leonhard Euler’s problem known as The Seven Bridges of Königsberg or is that a wholly different kettle of fish
LikeLike