Scientists Solve Most Complex Traveling Salesman Problem Ever
A new AI processor has extended the traveling salesman solution from 16 nodes to 22.
The traveling salesman is an age-old exercise in optimization, studied in school and relevant to "real life."
Rearranging how data feeds through the processor allows more than one thread to compute at a time.
Scientists in Japan have solved a more complex traveling salesman problem than ever before. The previous standard for instant solving was 16 “cities,” and these scientists have used a new kind of processor to solve 22 cities. They say it would have taken a traditional von Neumann CPU 1,200 years to do the same task.
The traveling salesman problem is centuries old, and it asks a deceptively simple question: For a salesman with a map of, say, 10 cities with given distances apart and roads connecting them, what’s the shortest path for the salesman to travel to every city and return home? The “deceptive” part is that the math to support the problem quickly grows overwhelmingly complex.
Each leg of the journey has a different length. Not all the cities connect to each other to form an ideal full star topology. And segments that connect, say, five cities have to somehow be compared to segments that connect three or eight. It’s just too variable, in both the proverbial and literal senses. A computer processor must calculate one full route at a time while storing the order of the points touched and the length of each leg of the journey.
The problem combines graph theory (the “map” of points with weighted legs between them) with combinatorics (the different ways you can count through a graph, in this case) and optimization (choosing the best, shortest route from a given graph). Because of this robust subject appeal, it’s been a favorite exercise in math and computer science classes of all kinds for many, many years.
The secret to these researchers’ success with the traveling salesman problem is in the special circuit they designed to calculate the routes. In a traditional computer processor, the routes must be arranged and then calculated and all passed through the processor one point at a time—the system is linear.
In most computing applications, we don’t notice that processing happens this way because the calculations are so rapid that they basically appear simultaneous. But the traveling salesman problem clogs the works because the number of calculations required is so huge. Adding more points on the map only increases the complexity. (Honestly, this news itself underlines how complicated the problem is: It’s major news to be able to solve just 22 cities instead of just 16!)
The researchers took a traditional circuit architecture and changed one critical thing: They rearranged special “spin cells” representing all the graph points so that the spin cells could all communicate with each other, not just the immediate surroundings connected by lines on the graph. This new arrangement allows routes to be made using multiple points at a time instead of just one, with fewer bottlenecks in the computational process.
The potential applications of a more powerful salesman solver are myriad. The abstract problem is infamous because it’s so widely studied and difficult, but its roots are still as an abstraction of a real person’s dilemma: How do I do my job the most efficient way? Every day, taxi and Uber drivers must consider the best route to find the most passengers. Delivery drivers must arrange their addresses in an efficient way. And these applications don’t just involve minimizing distance—fresh food or the value of a fare add even more complexity.
Suddenly, the 22nd address on the route is going to receive a much hotter pizza.
You Might Also Like
