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.