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

Various solutions are proposed for different problems.

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.

Related Links

Relationship between social problem solving and combinatorial optimization process

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!

Related Links

ACW Skills Roadmap

Have you read the article? Mark your skills roadmap.

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

SNS Sharing

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

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.

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