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:
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:
While satisfying this constraint, the combination of snacks that maximizes value is the answer you want to ask.
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 |
In IoT society where the real world and cyberspace cooperate with each other, the point of contact between people and the Internet space is not limited to edge terminals anymore -- such as personal computers and smart phones -- but spreads to the living spaces as well -- such as cars, houses, factories, offices, etc.
In an IoT society, we aim to analyze the vast amount of data collected by a large number of sensors and to optimally control the real world and various systems based on it. By doing so, our lives become more enriched, and we are expected to solve our social problems such as the declining birthrate and the aging population and the energy problem. In other words, technological innovation and creation of new jobs are carried out in a wide range of industrial fields such as manufacturing, logistics, retail, finance, transportation, social infrastructure, medical, agriculture, and healthcare and it is postulated that the industrial and economic structure of society as a whole will change drastically.
In such an IoT society, it is essential to search (quasi-) optimal solutions from among enormous
combinations quickly and accurately and to optimally control various IoT systems under a given
constraint condition.
For example, in the case of a logistic system, it is necessary to obtain a delivery route that
minimizes the delivery cost under the constraint of visiting all destinations. In machine learning
algorithms in artificial intelligence (deep learning etc.), it is necessary to perform optimization
processing in the learning process.
So, to attain new value and new services utilizing the IoT society, technology for processing combinatorial optimization problem with high efficiency will be the key.
On the other hand, for combinatorial optimization problems inherent in complex and large social systems, applying the method based on the conventional von Neumann type computer is difficult from the viewpoint of calculation efficiency and energy efficiency due to the exponential nature of the numbers of combinations (remember our traveling salesman problem?).
In 2030 when IoT spreads globally, the amount of data is expected to be more than 100 times the current amount. In order to process explosively growing big data at high speed and low power consumption and to perform optimum system control, fundamental and discontinuous innovation of computer hardware is required.
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.
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.