Sparsely Connected and Fully Connected (Part 1)
Overview
An annealing machine is a technique for solving combinatorial optimization problems through a mechanism in which the ground state of the Ising model (the state with the lowest energy) gives the optimal solution by setting preconditions that result in the optimal solution. To use an annealing machine, the problem must first be formulated as an Ising model.
In doing so, we need to understand what kind of Ising model structure the annealing machine we use is based on. Alternatively, the machine must be selected based on whether it is an annealing machine that can solve the problem you want to solve.
In this column, divided into the first and second parts, we will explain the structure of the model, which needs to be considered in the formulation and stage of selecting an annealing machine. The first part explains how to apply the Ising model to the problem to be solved (mathematical logic), and the second part explains the specifications of the annealing machine (implementation specifications).
Which spins are interacting with each other?
When selecting an annealing machine, "sparsely connected" and "fully connected" must be considered. The Ising model takes the form of a graph in which elements (vertices) called spins are joined by interactions (edges). The term "connection" refers to whether the spins of the Ising model are connected or not. In terms of the cost function equation, if there is a product of one spin and another spin, then the spins are "interacting," that is, "the spins are connected."
Image of sparsely and fully connected
Fully connected is also called dense connected?
In the sparsely connected Ising model, each spin is connected to some spins. In the fully connected Ising model, each spin is connected to all other spins.Incidentally, the term "densely connected" is sometimes used to describe the fact that a given spin is connected to many, but not all, spins. However, there is no clear definition of how many spins are needed to define something as sparsely or densely connected. Sometimes spins may be defined as sparsely connected when the number of connections are constant, and "densely connected" when the number of connections is increased in order; sparsely connected is when about 10% of the total spins are connected. Therefore, it is advisable to check the standard depending on the situation.
Examples of fully connected problems: Number Partitioning Problems and more
In the formulation, we formulated the number partitioning problem and derived the cost function $H = \sum(a_ia_j\sigma_i\sigma_j)$. This formula implies that all of the different elements must be multiplied together. We have seen that this is fully connected and that the number of interactions increases by $O(n^2)$ because $n(n-1)/2$ interactions must be entered for n number of elements. At this point, based on the number of interactions, we can determine if we can input them into the annealing machine.
Other problems that can be considered as fully connected problems include the problem of creating a timetable and the problem of creating a portfolio of stocks in the field of finance. For example, we discussed a timetable problem in the "organizing problems and defining requirements" , the relationship in which teachers of subjects are to be included in each class frame is considered in relation to the other frames. Also, in the portfolio creation problem, it is a fully connected problem because of the interrelationships that enter between all stock issues.
Examples of sparsely connected problems: signal control problems and others
The fact that there is only interaction between some of the spins in the Ising model is called sparsely connected. So what exactly is the sparsely connected problem?
In signal control optimization, we assign a binary value to the spin of whether a signal placed on a grid street is red or blue. (The exact definition is $+1$ for a vertical signal to be blue and $-1$ for a horizontal signal to be blue.)
Since those intersections are connected to each other only by vertical and horizontal roads, one spin is connected to only a limited number of spins representing neighboring intersections, so the relationship can be expressed by sparse coupling. Even if the grid of roads extends infinitely, the number of interactions required is no more than $2n$, as the number of intersection increases by $n$, since we know that for each additional intersection, there are two more adjacent roads. Even with 10 vertical x 10 horizontal = 100 intersections, the number of interactions is less than 200. In the number partitioning problem, 4,950 interactions are needed to split 100 numbers, so you can see how the structure of the Ising model makes a big difference.
Now, if some spins are connected on the cost function, but the corresponding spins are not connected (sparsely connected) on the Ising model used to implement the annealing machine, the problem cannot be solved as it is. In the following paragraphs, we will discuss some clues to determine the network structure of the Ising model when the need to optimize a particular problem arises.
The structure of the Ising model is based on either conceptual or physical events.
The fact that the number partitioning problems was solved by squaring the entire relational equation to obtain the product of all terms (i.e., the Ising model of all couplings with interactions among all spins) indicates that the fully connected Ising model is found in the connection among conceptual elements, i.e., variables. In such cases, the timing of the decision to determine that the structure of the Ising model is fully connected is in the middle of the formulation. Specifically, in the case of the number partitioning problem, it is "the time to make the energy function of the Ising model after the formulation of the relation.
On the other hand, in the case of the signal control problem, the fact that the decision to adopt a sparsely connected Ising model is made when the shape of the road is given as the problem, means that the sparsely connected Ising model is based on the connection of physical events such as grid roads. In other words, given the problem of optimizing signal control on a grid road, it is a good fit with the sparsely connected Ising model.
Consider the structure of the Ising model and make your choice!
We hope that you have now understood that there are differences in the structure of the Ising model depending on the problem. Although an annealing machine can dramatically reduce the time to obtain the optimal solution if only the Ising model can be used, the fact that there are differences in the form of the Ising model chosen for different problems is one of the items that should be considered to the maximum extent possible.
In the future, when using an annealing machine as a combinatorial optimization problem for new tasks, be aware of what structure of Ising model is chosen. Having that perspective is the first step in the attempt to use an annealing machine.
Summary
- A full connection in the Ising model means that every spin is connected to every other spin except its own.
- A sparse connection in the Ising model means that a spin is only connected to a specific spin.
- The fully connected Ising model can be said to represent the conceptual coupling of events, while the sparsely coupled Ising model represents the physical coupling of events.
Related Links
- Easy-to-learn optimization flow "Organizing problems and defining requirements"
- Easy-to-learn optimization flow "Formulation"
- Signal Control Optimization for Congestion Relief
