The Gap between Practice and Learning in the Traveling Salesman Problem

Overview

What is a typical combinatorial optimization problem? Many people may answer with the "traveling salesman problem". Although an annealing machine is said to be suitable for combinatorial optimization problems, it is not always the most effective method for solving real-world traveling salesman problems.

In this article, I would like to use the traveling salesman problem as an example to illustrate the gap between learning and practicing annealing machines.

The reason why the traveling salesman problem is often used to learn annealing machines

The traveling salesman problem is mathematically rewarding and has fascinated many mathematicians.

The traveling salesman problem is the question of "finding the shortest route that tours all the cities with only one visit to each of the $n$ cities." It is a favorite way to explain the difficulty of combinatorial optimization problems in a few words.

For example, if the number of cities is $n$, then $n!/2n$ calculations are required, and it is easy to imagine such a formula exploding with candidate solutions.

Problems that take a very long time to solve, i.e., problems that cannot be solved in polynomial time, are called "NP problems." And traveling salesman problems are said to be classified as "NP hard," meaning "as hard as or more hard than NP problems". The traveling salesman problem is often used to explain that there are computers that can solve the problem in a realistic amount of time.

A Mathematical Exploration of Solving Traveling Salesman Problems

There have been various studies to solve the traveling salesman problem (henceforth TSP) mathematically.

For example

In 1962, P&G offered a prize of $10,000 for the best solution to a TSP problem^*1.
A 49-city TSP was solved in the 1960s. And an ingenious addition of another method led to a record of 2,392 TSPs in the 1980s. In 2006, the program "Concorde" solved TSPs for 85,900 cities^*1,*2.

There also are various other studies about methods called "heuristics," e.g., greedy, local search, simulated annealing, etc. Heuristic methods do not necessarily find the optimal answer but can quickly find the correct answer to some extent.

Annealing machines are the devices that implement the theory of annealing with quantum spin or CMOS spin. It is thus a natural attempt to solve TSPs with annealing machines.

Gap between practice and learning

However, the mathematically theoretical solution may not be the primary option to solve real problems.

Since the TSP in the mathematical world is defined as a rigorous problem, it is worth solving because it must adhere to a given constraint (visit each city once). So there is an aspect bringing excitement to people by the academic progress of the increasing the number of cities that can be solved.

On the other hand, when considering real-world issues, there are many cases in which the TSP formula cannot be applied as is. For example, there is a less restrictive case, such as when "it is OK to go around the same place twice," or a more restrictive case, such as when "there is a specific order of going around."

Therefore, in conducting a realistic problem on searching for an optimal path, we combine mathematical methods and individual devices for the task at hand, depending on the number and complexity of constraints and the scale of the problem.

Determining the right tools for your practice

In some cases, as we have explained, there is a gap between "learning" and "practicing.

Skilled engineers search for and select the appropriate ways to solve a problem, and constantly update their knowledge and experience to improve the accuracy of their problem-solving abilities. The more complex a problem becomes, the more the engineer is required to spend time exploring the technology.

Annealing Cloud Web will actively provide information to engineers who are "problem solvers" about annealing machines and solving optimization problems that they may not be aware of ahead of time during the learning phase.

References

*1: Amazing Mathematics: The Traveling Salesman Problem by William J. Cook, translated by Shunsuke Matsuura, from Seidosha.
*2: Traveling Salesman Problem (uwaterloo.ca)