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)

Differences and complements between AI and Annealing Machines

If you want to know specific examples of solving combinatorial optimization problems with an annealing machine

What is a combinatorial optimization problem?

Combinatorial optimization will be explained by using two easy-to-understand examples of familiar combinatorial optimization problems. The importance of finding and using fast solution methods for combinatorial optimization processes in an IoT society will also be discussed.

Optimization of researcher shifts with consideration for COVID-19 infection control

In the wake of the COVID-19 epidemic, we present a use case in which an annealing machine is used to create shifts for researchers under constraints that take into account the risk of infection.

Optimize an insurer's reinsurance portfolio

This article presents a use case in which an annealing machine is used to formulate a reinsurance portfolio that leverages the vast amount of data held by an insurance company to address natural catastrophe risks.

If you want to know how to use an annealing machine

Easy-to-learn optimization flow

For beginners, this article explains the procedures and key points of the process of solving optimization problems with an annealing machine. The process involves dividing the problem into four stages: "organizing problem and defining problem," "formulation," "input data preparation," and "executing CMOS annealing machine".

Math for Annealing Machines

This article provides an easy-to-understand explanation of the mathematical assumptions you need to understand, focusing on "quadratic" and "discrete," which are some of the characteristics of the problems that annealing machines excel at solving.