Solving a combinatorial optimization problem with an annealing machine requires a process called Ising model formulation. This article describes the procedure.
To most effectively learn how to solve these problems, we use the number partitioning problem as an example of a simple Ising model, starting from defining requirements here as well.
A number partitioning problem is a problem in which the solution requires the division of several given numbers into two groups, $A$ and $B$. The sum of the respective numbers of those groups must be as equal as possible.
In the real world, for example, it can be used to figure out, "How do we divide the cargo between the two trucks"? The idea of making the sum of the numbers as equal as possible can be applied to considerations such as making the weight of the cargo in the two trucks the same or making the work time to load the cargo into the trucks the same.
Let us consider the formulation of the Ising model as a simple number partitioning problem, assuming that the following set $S$ is given. First, we define the requirements of the problem.
Let $S_A$ be the sum of the numbers in group $A$ and $S_B$ be the sum of the numbers in group $B$. Find the combination of the numbers for which $S_A=S_B$.
We are constructing an Ising model that expresses finding the combination of numbers resulting in $S_A=S_B$ as a cost function.
To express a cost function that satisfies $S_A=S_B$, we will formulate it as $S_A-S_B=0$.
First, we number each element in the integer pool to be partitioned, where i means the $i$-th element in $S$. In this example problem, there are nineteen numbers, so the range of $i$ is from 1 to 19; i.e., $i=1,2,3,...,19$. $j$ can be considered in the same way.
In the Ising model, the state of an element is called its spin, which can take on a value of either $+1$
In the number partitioning problem, we will set a spin $+1$ if the corresponding integer is in group $A$ and $-1$ if group $B$.
We will denote the variable representing the spin by $\sigma_i$, and call it the Ising variable.
Let us express the $i$-th number $a_i$ defined earlier to be in either group $A$ or $B$ as $a_i \sigma_i$. Because $\sigma_i$ can take either $+1$ and $-1$, the value of $a_i \sigma_i$ will be $+a_i$ if it is in group $A$ and $-a_i$ if it is in group $B$. If we distribute all the numbers into groups $A$ or $B$, the positive term in all the $a_i \sigma_i$ added together means an integer belonging to group $A$ and the negative term means an integer belonging to group $B$, thus representing $S_A-S_B$.
If we find $\sigma_1,\sigma_2,...,\sigma_N$ such that the sum of $S_A-S_B$ i.e., $a_i \sigma_i$ added from $i=1$ to $i=N$ equals $0$, then that should be an optimal solution.
Solving the Ising model with an annealing machine actually requires another twist.
The annealing machine tries to make several combinations, calculates the cost, and outputs the one with the smallest cost as the solution. To make the cost function that can gradually find the smallest value, we often square the original cost representation, resulting in a downward convex expression. In the case of this number partitioning problem, the closer $(SA-SB)^2$ is to $0$, the closer to the optimal solution. Also, when it reaches $0$, it is the optimal solution.
In other words, as a problem of minimizing $(S_A-S_B)^2=(\sum a_N\sigma_N)^2$, the number partitioning problem can be formulated in the Ising model.
If you have established an equation but are not very familiar with how to evaluate it mathematically, try
If you are unfamiliar with the expansion of the square formula, you can find references with the keywords "square expansion formula." See also the reference link at the bottom of this article.
Now, "$a$," which appears in this equation several times, cannot affect higher or lower in energy value of the cost function because it is a constant.
Therefore, we need only the terms for which the Ising variable $\sigma$ remains to observe the energy in
the Ising modeling.
Replacing only these terms in the $\sum$ equation yields;
(The reason we bother to correct it to $\sum$ is that it can be expressed in a shorter form. It is useful when programming.)
Furthermore, since 2 is not affected in obtaining the optimal solution whether it is there or not, it is the same if it is taken away.
This completes the formulation of the cost function of the Ising model for this number partitioning problem.
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.
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.
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.
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.