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}$
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
ACW Skills Roadmap
This article is part of the ACW Skills Roadmap. Use the skills roadmap to learn with ACW.
SNS Sharing
Did you find the article helpful? Please share it with others.
Related Articles
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.
Math for Annealing Machines
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.