Solve number partitioning problems with Ising editor!

Overview

EXECUTING CMOS ANNEALING MACHINE explains how to divide four numbers with a CMOS annealing machine from the WEB-API, but the same thing can be accomplished with the Ising editor. The Ising editor is a learning tool that provides a visual representation of the CMOS annealing machine in action, but it also doubles as a unique tool for visually seeing what to input to the CMOS annealing machine and how to obtain a solution.

• PREPARATIONBefore reading this page, please read FORMULATION and INPUT DATA PREPARATION.
• Intended audiencePeople who want to understand a little more about annealing machine processing before executing an annealing machine with WEB-API, and people who want to understand annealing machine processing without executing it themselves.

Prepare data (interactions) to be input into the Ising editor

An Ising editor value is a value assigned to a vertex or edge. A vertex in the Ising model is a spin variable that takes $s=±1;$ whether it is $+1$ or $-1$ is indicated by the result obtained by annealing. The value of the input to the vertex is the external magnetic field coefficient $h_i$. The external magnetic field coefficient $h_i$ represents the first order term in the cost function. Since there is no first-order term in the cost function of the problem we are solving, there is no value to be entered as the external magnetic field $h_i$.

On the other hand, the value to be entered as an edge is the interaction. Interactions are essential input data for an annealing machine.

In the Ising editor, the values that can be entered are limited to $-3, -2, -1, 0, 1, 2,$ and $3$. Therefore, both the interaction and the external magnetic field must be entered within these ranges.

Now we will prepare values that satisfy the cost function of the Ising model and the specifications of the Ising editor. First, the following equation was established as the Ising model for the cost function of the number partitioning problem. In this problem, $a_ia_j$ is the interaction (input data preparation).

Let us now determine the number of divisions to be made. The interaction constraint is $-3 ≤ a_i a_j ≤ 3$ ($a_i a_j$ is an integer), so here we calculate all the interactions for splitting the four numbers $(a_1,a_2,a_3,a_4)=(-1,-1,1,2)$. Divide them into two groups so that the sums are as equal as possible, there should be a group with a total of 1 and a group with a total of $0$. We can also assume what would happen if the results were bad. If the total is divided into two groups of $3$ and $-2$, respectively. First, name the elements as follows, and then use the diagram to determine which interactions should be placed where in the Ising editor.

You can see that the lattice Ising editor allows you to enter interactions for all four number divisions; there are six of them.

Each interaction of $J_{12}, J_{13}, ...$ is as follows.

Enter the ising editor with that arrangement. It will look like the following

Here we see that if we had chosen two or more 2s or 3s at the same time for the number to be divided, we would need 4s, 6s, or 9s as interactions, so we would not be able to enter them.

STEP UP

Common mistake: wouldn't you enter the number of vertices you want to divide in the Ising editor?

The input to the vertex is the coefficient $h_i$, the external magnetic field coefficient, not the number you want to divide. If the cost function has a first order term (= only one term with $\sigma$ instead of two), this coefficient is the external magnetic field coefficient. In the cost function of a number-splitting problem, there is only a term of the second order (= two terms multiplied by two $\sigma$). Therefore, it is correct to enter nothing at the Ising editor vertices. As an example, the cost function below has an external magnetic field coefficient of 3.

Frequently Asked Questions: Why did you arrange the grid without entering the number of divisions needed in the Ising editor?

That is because the placement of the interaction coefficients is important. Interactions are meaningless unless they are aligned not only in value but also in position. If the values are the same but the positions are lousy, the assumption that it is the number you want to divide is broken.

Execution

Press the Run button.
The OUTPUT window will show the orientation of the spins. It means that spins with the same orientation will be in the same group.

The above case is divided into $(-1,2)$ and $(-1,1)$. The numbers sum to $1$ and $0$, respectively.

After that, you can press the Run button as many times as you like, sometimes exactly the same as the first time.

In the above case, the position has changed, but the two $-1$'s have just been exchanged. The sum of the numbers is $1$ and $0$ respectively.

In the above case, it was divided into 1 and 3. The total is only $1$ for the upward ↑ group and $(-1,-1,2)$ for the downward ↓ group, so their sum is $0$.

Interesting, there are some like this. All of them are now in a downward group. The total is $1$ because $(-1,-1,1,2)$, and the other group has no elements, so the total is $0$. The other group has no elements, so the sum is 0.

No matter how many times I run it, the total is never split between $3$ and $-2$. It appears that we have successfully optimized the system.

What happens if I put in the wrong value?

Even if the wrong value is entered, the execution process will still be performed. In other words, if you enter a different value for the edge than the value obtained by multiplying the number of values you want to divide by, you will not get an error, and the spin will be determined and OUTPUT for the time being. In that case, however, the direction of the spin is meaningless. It is important to input the exact value in order to obtain a solution.

Summary

• The solution obtained by the optimization process of the annealing machine is a combination of which spins are upward or downward.
• The Ising editor can solve the Ising model problem by entering spin external field coefficients and interaction coefficients between -3 and 3.
• The solution (spin direction) that emerges from each run is different, but the energies are all minimal, indicating that an optimal solution^* is obtained.
  *Inherently, only the optimal solution is not always derived, and this result shows only the optimal solution due to the small size of the problem.
• If you put in the wrong input data, it will not return an error.

Related Links

• Executing CMOS annealing machine
• Sparsely Connected and Fully Connected (Part 1)
• Sparsely connected and Fully connected (Part 2)