Executing CMOS annealing machine
Overview
Let's input the data for the number partitioning problem created in the "Input Data Preparation" section into the CMOS annealing machine to solve it. For simplicity, we will describe the process of running the problem on a CMOS annealing machine using the four spins of the CMOS annealing machine.
When the number partitioning problem is viewed as an Ising model in the formulation process, the interaction is the element that corresponds to the spins, i.e., each number is multiplied evenly. An Ising model in which there is an interaction between all spins is called an Ising model of total coupling. Our CMOS annealing machine is sparsely-connected with a King's graph. The number-partitioning problem was found to be fully-connected during the formulation process, but you can also input any four number-partitioning problems to King's graph.
Preparation of Development Environment
Up to this point, we have only studied the theory, but from here on out, we need to operate the CMOS annealing machine. First, this article will briefly explain how to prepare the development environment.The CMOS annealing machine can be operated by using the WEB API (Application Programming Interface). The procedure is as follows.
CMOS annealing is accessed through the Web-API. If you have an environment that you are comfortable with, please use it. As an example, we show here how to use Jupyter Notebook on a Windows-PC.
1. Installation of Python3
Download the latest version here. Select the one that matches your PC specs.
2. Install Jupyter Notebook from the command prompt.
Jupyter Notebook is an interactive programming execution environment that runs in a browser. Since only very simple functions are used here, please refer to the official Jupyter Notebook site for installation by pip.
3. How to start and exit
Start Jupyter Notebook from the command prompt with "Jupyter Notebook".
To exit, press Ctrl + C at the command prompt.
Once you are able to successfully launch Jupyter Notebook, let's proceed with the exercise.
4. Obtaining an API Token
To access CMOS Annealing, you must obtain an API token for use with the Web-API. Request a API token from the following page. Don't forget to fill out the questionnaire.
https://annealing-cloud.com/en/web-api/token-request.html
Modeling to Ising model and input data preparation for number partitioning problem with four numbers
Now let's quickly create the input data. First, suppose we are given the set $S = \{13, 9, 8, 5\}$. We know that the optimal solution is $S_A = \{13, 5\}$ and $S_B = \{9, 8\}$, since we will divide it into two groups. Can we successfully divide them by CMOS annealing?
Number the elements.
| a1 | a2 | a3 | a4 |
| 13 | 9 | 8 | 5 |
Then list the interactions.
$$ J_{12} = a_1*a_2 = 117 \\ J_{13} = a_1*a_3 = 104 \\ J_{14} = a_1*a_4 = 65 \\ J_{23} = a_2*a_3 = 72 \\ J_{24} = a_2*a_4 = 45 \\ J_{34} = a_3*a_4 = 40 $$
You have listed everything.
Address Translation (for CMOS annealing machines)
How to specify spin coordinates in a CMOS annealing machine
Now, we will input this data to the CMOS annealing machine. The CMOS annealing machine's Ising model is a King's graph, which means that it is represented as a sequence of spins on the $x$ and $y$ coordinates. The specifications of the annealing machine are $512 \times 512 = 256,000$ spins for the GPU version and $384 \times 384 = 147,456$ spins for the ASIC version. Four of those spins must be arranged in such a way that they interact with each other. Also, it would be quicker to describe them as set on the 0 and 1 axes, which is easy on the input.
For example, the spin interacting with the spin $(0,0)$ is assumed to be adjacent to $(1,0)$ or $(0,1)$, etc. If the spins are not adjacent, an error will occur when inputting the data to the CMOS annealing machine.
In the figure above, the intention is to place the elements of numbers in the annealing machine as an Ising model, so instead of $a_1$ to $a_4$ representing the elements of numbers, $\sigma_1$ to $\sigma_4$ represent the spins.
Creation of input data for interactions
In CMOS annealing machines, interactions are represented this way.
The following is the JSON description.
coefficients = [ [0, 0, 0, 1, 117], [0, 0, 1, 0, 104], [0, 0, 1, 1, 65], [0, 1, 1, 0, 72], [0, 1, 1, 1, 45], [1, 0, 1, 1, 40], ]
Other Settings
Parameter setting
Let's create it with standard parameters. The term "parameter" refers to a numerical value that specifies
a temperature
schedule, which can be specified by "initial temperature," "final temperature," "step length," and "number
of steps."
For a detailed explanation, please refer to the Ising Editor
tutorial.
For now, we will use the same parameters as in the API reference.
Select a machine
Annealing Cloud Web currently offers two types of machines to choose from. In this case, we will use the GPU version, which can use larger interactions coefficients.Type is 3.
We set these up and created the following data to be run in Python. The input data is set in this variable input_data.
Setting example
# parameters
num_executions = 5
temperature_initial = 30
temperature_target = 0.0000001
machine_type = 3
input_data = {
"num_executions": num_executions,
"model": coefficients,
"type": machine_type,
"parameters": {
"temperature_initial": temperature_initial,
"temperature_target": temperature_target,
},
}
The configuration for execution is as follows, where XXXX... is the API token you obtained.
import requests
import json
# API token
token = "XXXXXXXXXXXXXXXXXXX"
headers = {'Authorization': 'Bearer {}'.format(token)}
# CMOS Annealing Machine address
CMOSannealing_url = 'https://annealing-cloud.com/api/v2/solve'
execution (e.g. program)
Once we have prepared up to this point, all that remains is execution. Let's execute it as follows.
r = requests.post(CMOSannealing_url, headers=headers, json=input_data) result_sigma = r.json() print (json.dumps(result_sigma))
The following results will be returned when you run the machine, although they will not necessarily be the same every time because CMOS annealing uses random numbers. They will be in the following form.
{
"status": 0,
"result": {
"energies": [-169.0, -169.0, -169.0, -169.0, -169.0 ],
"execution_time": 278175600,
"spins": [
[[0, 0, -1], [1, 0, 1], [0, 1, 1], [1, 1, -1]],
[[0, 0, 1], [1, 0, -1], [0, 1, -1], [1, 1, 1]],
[[0, 0, 1], [1, 0, -1], [0, 1, -1], [1, 1, 1]],
[[0, 0, -1], [1, 0, 1], [0, 1, 1], [1, 1, -1]],
[[0, 0, -1], [1, 0, 1], [0, 1, 1], [1, 1, -1]]
],
"job_id": "95c834c3-7d8a-4c32-8560-fd4d6fdddfb2"
}
Confirmation of output results
Also refer to the Web API "Response" to check the results.
Energy is displayed first, 5 annealing runs have been performed, all of which resulted in $H = -169$. The execution time is in nsec. The above result shows that the solution took about 0.27 seconds. There is no error message and it is successful.
For the optimal solution we look at the SPINS, where the first solution is $[[0, 0, -1], [1, 0, 1], [0, 1, 1], [1, 1, -1]]$. Check the numeric elements assigned to the vertices of the Ising model by looking at them again.
The solution shows us that $\sigma_2$ and $\sigma_3$ assigned to $1$ are in the same group, and
$\sigma_1$ and $\sigma_4$ assigned to
$-1$ are in the same group. The total is $17$ for the former and $18$ for the latter, so the solution is
as expected.
Then what is the energy when we input it into the cost function?
$$ \begin{align*} H &= a_1a_2\sigma_1\sigma_2 + a_1a_3\sigma_1\sigma_3 + a_1a_4\sigma_1\sigma_4 + a_2a_3\sigma_2\sigma_3 + a_2a_4\sigma_2\sigma_4 + a_3a_4\sigma_3\sigma_4 \\ &= 13\times9\times(-1)\times1 + 13\times8\times(-1)\times(1) + 13\times5\times(-1)\times(-1) + 9\times8\times1\times1 9\times5\times1\times(-1) + 8\times5\times1\times(-1) \\ &= -117 - 104 + 65 + 72 - 45 -40 \\ &= -169 \end{align*} $$
You see that $H = -169$, which is the energy obtained by the CMOS annealing machine.
Thus, a simple number partitioning problem with four elements gave us an idea of how to use a CMOS
annealing machine.
It would be a beneficial to check what happens to the other solutions derived from the five annealings.
Also, experiment with different numbers to divide and see if the results change. If the number is not large, then an ASIC version of the CMOS annealing machine may be used. In some cases, you may also want to change the machine on which it is run.
summary
- Since the Ising model for the number partitioning problem is fully-connected, we solved the four number partitioning problem to place it into a CMOS annealing machine that is implemented in a sparsely-connected manner.
- In CMOS annealing machines, the spin and interaction of the Ising model is specified in $x$ and $y$ coordinates as $[a_{xi}, a_{yi}, a_{xj}, a_{yj}, J_{ij}]$.
- The output of CMOS annealing confirms that the number partitioning problem is solved.
Related Links
Next Steps
Take your learning one step further by experiencing the development flow of a combinatorial optimization system using a CMOS annealing machine through a series of steps from problem definition to implementation.
Signal Control Optimization for Congestion Relief
This article provides an exercise to realize a signal control system to relieve traffic congestion as a signal control system by processing it with a CMOS annealing machine as a combinatorial optimization problem.
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.
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.
Optimize an insurer's 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.