What is the combinatorial optimization problem

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.

Knapsack problem

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:

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.

Traveling salesman problem

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

Relationship between IoT society and combinatorial optimization processing

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.

Next Steps

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.

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.