Formulation
Overview
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.
Theme: Number Partitioning Problem
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.
STEP 1. Defining requirements
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.
Requirements
- When dividing a set of integers $S$ into two groups, $A$ and $B$, find a combination that makes the sum of the integers in the two groups $A$ and $B$ as equal as possible.
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$.
STEP 2. Formulation
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$
or $-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$.
$$ \sum a_i \sigma_i = S_A - S_B \to 0 $$
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.
STEP 3. One more twist on the cost function
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
writing it
down.
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.
$$ \begin{align*} (S_A-S_B)^2 &=(\sum a_i\sigma_i)^2 \quad \scriptsize \text{\# If i is between 1 and 3 (a set consisting of 3 numbers)} \\ &=(a_1\sigma_1 + a_2\sigma_2 + a_3\sigma_3)^2 \\ &={a_1\sigma_1}^2 + {a_2\sigma_2}^2 + {a_3\sigma_3}^2 + 2a_1a_2\sigma_1\sigma_2 + 2a_1a_3\sigma_1\sigma_3 + 2a_2a_3\sigma_2\sigma_3 \\ &={a_1}^2 + {a_2}^2 +{a_3}^2 + 2a_1a_2\sigma_1\sigma_2 + 2a_1a_3\sigma_1\sigma_3 + 2a_2a_3\sigma_2\sigma_3 \quad \scriptsize \text{\# σ \textasciicircum2=1, so it can be omitted.} \end{align*} $$
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.
$$ H = \sum(a_ia_j\sigma_i\sigma_j) $$
Summary
- In the Ising model, the state of an element is called its spin, which can be either $+1$ or $-1$
- Represent the problem with spin
- Express the cost function in a square equation, which an annealing machine can handle.
