A combinatorial optimization problem is the act of trying to **find out the value (combination)
of variables that optimizes an index (value) from among many options** under various
constraints.
In this section we will walkthrough two examples of familiar combinatorial optimization problems that
are easy to understand. After that, we will describe the importance of having a method of
combinatorial optimization processing in IoT society and what the benefits are of solving these types
of issues as quickly as possible.

Everyone has experienced solving combinatorial optimization problems in various situations of
everyday life. Let's recall, for example, a picnic snack selection when you were a child (Knapsack
problem).

In this case, variables, constraints, and values are:

**Variables**: Snack you choose**Constraints**: Money in your pocket**Indicator (value)**: Total degree of satisfaction

Item | Variable | Price | Satisfaction |
---|---|---|---|

Chocolate | $x_1$ | 120 JPY | 10 points |

Candy | $x_2$ | 30 JPY | 3 points |

Cookie | $x_3$ | 90 JPY | 4 points |

Chips | $x_4$ | 150 JPY | 8 points |

Jelly beans | $x_5$ | 120 JPY | 7 points |

Here we shall limit ourselves to buy two or fewer of each snack. In order to improve visibility, let's
introduce variables$x_1, x_2,⋯x_5∈ {0, 1},$ 0: Reject, 1: Choose, and express snacks selection problem
by mathematical expression.

At this time, the value (satisfaction level) and the constraint (the money in your pocket) are as
follows:

- Value: $10x_1 + 3x_2 + 4x_3 + 8x_4 + 7x_5$
- Constraint: $120x_1 + 30x_2 + 90x_3 + 150x_4 + 120x_5\leq300$

While satisfying this constraint, the combination of snacks that maximizes value is the answer you want to ask.

- Answer: Chocolate, candy, and chips (satisfaction 21 points, total amount 300 JPY)

In the example given here, there were only five types of snacks and it was very simple, but it can quickly grow in scope and complexity. In fact such a problem appears in various scenarios in the real world. For example, there is a problem "investment destination selection problem" to find a combination of opportunities that maximizes expected profit (value) with a fixed budget (constraint) when necessary expenses and expected profits of each case are given.

As another example of the combinatorial optimization problem, let's think about the traveling
salesman problem (delivery route problem).

This problem is a question of how the salesman should navigate for the shortest traveling route
(optimal route) when visiting multiple cities when given a list of inter-city distances.
A major caveat is that he will visit each city only once. If the number of cities is small, it is
possible to investigate all the solution candidates.
However, as the number of cities increases to 30 cities, for example, meaning the number of
candidates has increased, meaning the combination becomes the phenomenal number of 10 to the 30th
power.
In this case, to comprehensively list all solution candidates and to find the optimum route, even
if using a supercomputer, will take the astronomical time of 14 million years!
So the obvious characteristic of the combinatorial optimization problem is that it becomes very
difficult to obtain an exact solution as the number of parameters increases.

Route | Moving distance | |
---|---|---|

Route 1 | ABCDE(A) | 22 |

Route 2 | ABCED(A) | 24 |

Route 3 | ABDCE(A) | 20 (Shortest route) |

ABDEC(A) | 26 | |

ABECD(A) | 22 | |

ABEDC(A) | 26 | |

Route M | ACBDE(A) | 25 |

ACBED(A) | 27 |

The method of solving a combinatorial optimization problem is quite different between the snacks selection problem and the traveling salesman problem. As mentioned above, the solution of the snacks selection problem can be expressed by a mathematical formula that can be learned in junior high school, and a spreadsheet solver can be used to solve the problem according to this formula. Alternatively, you can obtain the value by drawing a graph as you learned in school. On the other hand, in the case of the traveling salesman problem, it has been found that the exact solution cannot be obtained efficiently by examining the combinations of 30 cities in a single step. In such cases, a solution method called heuristic has been studied. Furthermore, it has been found that combinatorial optimization problems with certain conditions can be solved efficiently using an annealing machine, and research is being conducted from various perspectives to find out what kind of problems can be solved efficiently using an annealing machine, and whether there are effective ways to use an annealing machine. Research is being conducted from various perspectives to determine how annealing machines can be applied to solve social problems efficiently and to find effective ways to use annealing machines.

- Heuristic solution
- Math for Annealing Machine
- The Gap between Practice and Learning in the Traveling Salesman Problem

In the past few years, dedicated hardware for solving combinatorial optimization problems at high speed has been continuously introduced and studied. Annealing machines are computers being developed for a specific application: combinatorial optimization. It has been about 40 years since the simulated annealing method, on which the theory is based, was first proposed. Although the number of cases in which dedicated annealing machine hardware is actually being used for information processing in our daily lives is still limited, we are now at the stage of its introduction and expansion into industries and economic activities that are familiar to our daily lives.

This is due to the fact that various external factors, or social issues, are also becoming more serious. For example, the shortage of drivers and the reduction of CO2 emissions have become issues in response to the increase in logistics, and the optimization of logistics operations and transportation routes has become a pressing issue.

On the other hand, until now, combinatorial optimization processing has been performed using general-purpose computers with software implementation of heuristics and other methods of solving problems, but performance has reached its limits in solving the growing number of social issues. Therefore, research and development of new hardware, or annealing machines, to break through these limitations is now in full swing.

With the progress in research and development of annealing machines, the business side of industry is beginning to consider innovative services. For example, annealing machines can simulate reinsurance portfolios and prepare the social infrastructure to withstand changes in disaster risk.

For annealing machines to mature as a powerful tool for solving social issues, stakeholders on both the use side (Business) and the creation side (Engineer) must cooperate with each other to accelerate creative and challenging efforts.

Learn and experience the various possibilities of annealing machines on the Annealing Cloud Web, and discover the power of combinatorial optimization yourself!

- ACW Skills Roadmap
- Optimization of researcher shifts with consideration for COVID-19 infection control
- Optimizing reinsurance portfolio

This article is part of the ACW Skills Roadmap. Use the skills roadmap to learn with ACW.

Did you find the article helpful? Please share it with others.

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

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.

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

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".

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.