Transcript
How would you go about returning books to the correct shelves in a large library with the least amount of walking? How would you determine the shortest route for a truck that has to deliver many packages to multiple cities? These are some examples of the “traveling salesman problem,” a type of “combinatorial optimization” problem, which frequently arises in everyday situations. Solving the traveling salesman problem involves searching for the most efficient of all possible routes. As everyone who has ever taken a business school “operations management” class knows, this quickly becomes an overwhelming challenge for humans or conventional computers.
To solve this conundrum, scientists are actively exploring the use of special-purpose integrated circuits. With this method, each state in a traveling salesman problem (for example, each possible route of the delivery truck) is represented by “spin cells,” each having one of two states. Here a circuit that can store the strength of one spin cell state over another represents the distance between two cities for the delivery truck. Using a large system containing the same number of spin cells and circuits as the cities and routes for the delivery truck, we can identify the state requiring the least energy, or the route covering the least distance, thus solving the traveling salesman problem or any other type of combinatorial optimization problem.
However, a major drawback of the conventional way of using integrated circuits to do this is that it requires pre-processing, and the number of components and the time required to input the data increase as the scale of the problem increases. For that reason, this technology has only been able to solve a traveling salesman problem involving a maximum of 16 cities.
However, a group of Japanese researchers aimed to overcome this constraint. They observed that the interactions between each spin cell are linear, which ensured that the spin cells could only interact with the cells near them, prolonging the processing time. So, they decided to arrange the cells differently to ensure that all spin cells could be connected to each other.
To do this, they first arranged the circuits in a two-dimensional array, and the spin cells were arranged separately in a one-dimensional arrangement. The circuits could then read the data and an aggregate of this data was used to switch the states of the spin cells. This means that the number of spin cells required, and the time needed for processing were both drastically reduced.
The researchers presented their findings at the IEEE’s 18th World Symposium on Applied Machine Intelligence and Informatics. The new technique constitutes a fully coupled method and has the potential to solve a traveling salesman problem involving up to 22 cities. The team is hopeful that this technology will have future applications as a high-performance system with low power requirements that will enable office equipment and tablet terminals to easily find optimal solutions for a wide range of combinatorial business problems.
|
