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.
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.
Download the latest version here. Select the one that matches your PC specs.
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.
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.
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
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.
You have listed everything.
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.
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], ]
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.
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.
# 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'
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" }
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?
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.
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.
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.
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.
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.
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.
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.