Chapter 1: Solving Combinatorial Optimization Problems

Before going on to solve problems with annealing machines, users will first consider what it takes to apply the discipline of mathematical optimization to real-world problems. Those who have already used mathematical optimization to solve real-world problems may skip this chapter.

First, in order to use an annealing machine, it is necessary to define the problem and formulate it into an Ising model. The optimization process, not limited to an annealing machine, involves replacing the phenomenon that represents the problem to be solved with a mathematical expression. For more details on the optimization process in an annealing machine, please check Organizing Problems and Defining Requirements, Formulation, Chapter 2, Section 2.

Now, before we formulate the mathematical optimization problem we are trying to solve, we will explain the knowledge needed to determine if it is the type of combinatorial optimization problem that can be successfully solved using an annealing machine.

In your mathematics classes at school, you have solved a variety of problems and learned that a linear equation is represented by the line y = ax + b. You have also applied your knowledge of linear equations to solve problems that maximize or minimize a region. Applying the knowledge of linear equations to solve optimization problems is the concept of linear programming in mathematical optimization (explained in Chapter 3, Section 1). In a combinatorial optimization problem solved by an annealing machine, a number of discrete parameter combinations (ranging from tens, hundreds, to millions, depending on the task) are compared and the best possible combination is chosen. Keep in mind that discrete parameters mean that the values are scattered rather than connected in a straight line, so if you have many combinations of parameters to optimize, finding the right combination can be a challenge. To get a feel for the difficulty of such problems, it is not practical to solve them by hand, so you can get a feel for the difficulty by solving them using programming or algorithms.

The history of optimization began with linear programming problems. Later, algorithms for solving optimization problems were created and then solved by computers. Algorithms for solving even larger combinatorial problems were also studied.

When we aim to solve a problem, we apply an algorithm, run on a computer, to reach our solution. When we have an optimization problem that we want to solve, we need to learn how to solve various problems and then we need to actually solve them in order to know whether we can solve it successfully using an annealing machine or whether we need a different method. In order to efficiently learn the process that will help you understand annealing machines, it is necessary to acquire a wide range of knowledge, especially mathematics. That is why we have compiled "Math for Annealing Machine" to help users learn about annealing machines with as little resistance as possible. We will continue to add to and revise this document to provide more complete explanations.

What is the cost function?

ACW Skills Roadmap

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

Go to the skills roadmap

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

What is the 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.

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