Input Data Preparation

Overview

In this article, we will create input data for the number partitioning problem that we have made "formulation" in the previous article. Creating input data is a routine task, but this article will cover its important fundamental topics.

STEP 1: Input data is a list of $J_{ij}$
STEP 2: Let's calculate $J_{ij}$.
STEP 3: The amount of data grows faster than that of the elements.

STEP 1: Input data is a list of $J_{ij}$

In the formulation, we considered the Ising model and defined a cost function $H$.

The indices $i$ or $j$ means the $i$-th or $j$-th element in $S$. In this number partitioning 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.

We formulated the Ising variable $\sigma_i$ ("spin") to indicate whether the $i$-th element is placed in $S_A$ or $S_B$, as $\sigma_i=+1$ when placed in $S_A$ and $\sigma_i=-1$ when placed in $S_B$.

In this case, to compute the cost function $H$ for some combination $\sigma_1, \sigma_2, ..., \sigma_N$, we need to know the values of $a_i a_j$. The set of values calculated for every possible combination between $i$ and $j$ is the input data to an annealing machine, which is also called $J_{ij}$.

$$ J_{ij} = a_ia_j $$

By the way, what does $J_{ij}$ mean?

If the left figure below represents the entire Ising model, one $J_{ij}=a_i a_j$ can be thought of as representing the strength of the influence between the Ising variables $\sigma_i$ and $\sigma_j$, as shown in the enlarged figure on the right. This force between spins is called the interaction.

Relationship between the cost function and the Ising model

The optimization process of an annealing machine is to find the lowest cost combination of $\sigma_1, \sigma_2,...$ when assigning $+1$ or $-1$ for each of the variables. The information given to calculate the cost is $J_{ij}=a_i a_j$, i.e., the interaction. The input data that the annealing machine needs are the interactions.

STEP 2: Let's calculate $J_{ij}$.

Let us calculate the interaction $J_{ij}$ in the number partitioning problem.

All interactions to be given are obtained by multiplying elements 1 through 19 evenly, as shown below.

$$ J_{12} = a_1 \centerdot a_2 = 3 \times 1=3 \\ J_{13} = a_1 \centerdot a_3 = 3 \times 4=12 \\ J_{14} = a_1 \centerdot a_4 = 3 \times 15=45 \\ \centerdot \\ \centerdot \\ \centerdot \\ J_{1819} = a_{18} \centerdot a_{19} = 28 \times 84=2,352 $$

Although omitted in the figure, the total number of interactions is $19 \times (19-1)/2 = 152$. $152$ values must be entered into the annealing machine.

STEP 3: The amount of data grows faster than that of the elements.

When the computational complexity increases in proportion to the square of the number of elements, we say that the $\mathcal{O}$ (order: computational complexity) is $N^2$ in the mathematical expression. In other words, in the number partitioning problem, we can say that the order of interaction of the Ising model is $N^2$.

In the formulation of the number partitioning problem, all the elements are connected to each other (fully coupled), so the interaction is required for elements $x$ elements. As shown in the figure above, even for 19 elements, 152 interaction coefficients for the Ising model are required. If the number of elements were 100, the number of interaction would be $100(100-1)/2 = 4950$.

If the formulation can be made simple in terms of the relationship between elements, i.e., no multiplications appear, then the number of interactions can be reduced and the input data can be reduced. Incidentally, when any elements can interact with each other, it is considered "fully coupled".

Summary

Creating input data means calculating all of the $J_{ij}$
Input data are values that represent the interaction and may increase by an order of magnitude of the square as the number of elements increases
If the relationship between elements is on the simpler side, the number of interactions may by smaller

References

Formulation

Executing CMOS annealing machine

If you want to know specific examples of solving combinatorial optimization problems with an annealing machine

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