Benchmarking the MAX-CUT problem on the Simulated Bifurcation Machine

Published in

Toshiba SBM

6 min readSep 30, 2019

Abstract

Using the Simulated Bifurcation Machine (SBM) published by Toshiba Digital Solutions Corporation on the AWS Marketplace, we have performed benchmarks of the combinatorial optimization problem MAX-CUT.

The Simulated Bifurcation Machine

SBM is a solver for combinatorial optimization problems provided by Toshiba Digital Solutions Corporation. By taking methods from classical physics used to describe bifurcation phenomena, adiabatic processes and Ergodic (or later chaos) theory and applying them to combinatorial optimization, SBM solves large problems quickly.

A proof-of-concept version is available on the AWS marketplace.

The MAX-CUT problem

We chose the MAX-CUT problem as a representative combinatorial problem that the SBM can solve.

The objective of the MAX-CUT problem is to split a graph into two mutually exclusive subgraphs such that the cumulative weight of inter-subgraph edges is maximal.

Objective function

Consider the case where we split graph V into the subgraphs S and T.

We define the binary value sᵢ, also called Ising variable, to express which subgraph vertex vᵢ∈V is in as follows

Using this variable, we define the objective function of the optimization problem as follows

where Wᵢⱼ is the weight of the edge between vertices vᵢ and vⱼ. Only in the case where vᵢ, vⱼ are in opposing subgraphs is

When the two vertices are in the same subgraph, the weight of the edge connecting them will be multiplied by 0. Thus, maximizing this function will yield the solution to the MAX-CUT problem.

In annealing machines, the objective function is commonly minimized, not maximized. Multiplying the objective function by -1 lets us treat this is a minimization problem.

Additionally, defining a true binary

Based on the Ising variable, we can rewrite the objective function as follows

This function can be used on annealing machines that expect true binaries like qᵢ.

Executing the SBM

MAX-CUT mode

The SBM includes a specialized MAX-CUT solver (MAX-CUT mode) that takes text input describing the problem. For the text input, the SBM supports the MatrixMarket format as well as that of the MAX-CUT benchmark dataset Gset.

The structure of the Gset format, which uses white space as separation for a list of integer values, is shown below

N E
i0 j0 w_i0j0
i1 j1 w_i1j1
i2 j2 w_i2j2

The first row lists the number of vertices N and edges E, while following rows list the edges one edge per row. Each such row contains the edge’s endpoint vertices i and j as well as its weight wᵢⱼ.

As an example, the following shows a MAX-CUT problem with 5 vertices and 7 edges in Gset format

Visualizing this as a graph results in the following figure.

The SBM parameters

The following parameters can be posted to the SBM.

steps: The number of steps in the SBM calculation. The default is 0, in which case the number of steps is dynamically determined.
loops: How many times the SBM calculation will be repeated to find better solutions. The default is 1, and a value of 0 will have the SBM run until the timeout time.
timeout: The maximum calculation time in seconds. If executing the next loop would likely cause the SBM to overstep the timeout, calculations will be terminated early.
target (optional): When a value is specified, execution will terminate when the objective function reaches said value.
stats: The detail level of the statistical output returned. Statistics are collected over the loops*steps executions. Possible values are
none: Return no statistical output.
summary: Return average, standard deviation, and best frequency.
full: Return average, standard deviation, and a histogram.

Executing the example with five vertices from above-using curl looks as follows

$ echo -e "5 7\n1 2 1\n1 5 1\n2 3 -1\n2 4 1\n2 5 -1\n3 4 -1\n4 5 1" | curl -i -H "Content-Type: application/octet-stream" -X POST "http://192.168.0.1:8000/solver/maxcut?steps=0&loops=0&timeout=1&stats=full" --data-binary @-

Note that the IP-address (here 192.168.0.1) varies based on your environment.

We are using the parameters listed below

steps = 0
loops = 0
timeout = 1
stats = full

If execution is successful, the SBM will send the following response.

HTTP/1.1 200 OK
    Content-Type: application/json; charset=utf-8
    Content-Length: 233
    ETag: W/"e9-6jYjTGcvinFBL6/eKnutYNzItOQ"
    Date: Mon, 19 Aug 2019 03:59:29 GMT
    Connection: keep-alive{"id":"r1477108799","time":1,"wait":0,"runs":396800,"steps":10,"message":"timeout","value":3,"result":[0,1,0,0,1],"stats":{"avg":2.441142,"stddev":1.372172,"histogram":[[-2,24009],[-1,4124],[0,15682],[1,12766],[2,12636],[3,327583]]}}

The central parts of the JSON response are the following

result: The best solution found
value: Value of the objective function for the best solution
runs: Amount of executions (loops*steps)

Benchmarking with Gset

We will now execute the MAX-CUT benchmark dataset Gset, which can be downloaded from http://web.stanford.edu/~yyye/yyye/Gset/.

Gset consists of the problems G1 to G81 and, due to some skipped numbers, has a total of 71 problems with a graph size ranging from 800 to 20,000 vertices. There are graphs without weighted edges (all weights are 1) as well as graphs with weighted edges where the weights are either +1 or -1. Geometrically, the structure of the graphs can be split into three categories

Random graphs
Planar graphs
Toroidal graphs

Execution commands

For ease of use, we employ curl to post the Gset dataset to the SBM. For example, to execute problem G1 with the parameters steps=0, loops=0, timeout=10 and target=11624, navigate to the directory where the Gset dataset is stored and execute the following command

$ cat G1 | curl -i -H "Content-Type: application/octet-stream" -X POST "http://192.168.0.1:8000/solver/maxcut?steps=0&loops=0&timeout=10&target=11624" --data-binary @-

Benchmark results

The following lists the results for 69 graphs in Gset. All executions were done with the parameters
steps=0(automatic), loops=0(automatic), timeout=10 and target=(best-known), where best-known refers to the best-known values of the objective function for the given problem, which were taken from previous research.

For smaller graphs, the preset optimization target was reached in less than one second in most cases.

For the above benchmark, we have let the system determine the appropriate number of steps automatically. However, we suspect that higher performance can be achieved by specifying the amount of steps a priori. To test this hypothesis, we have executed problem G65 with a time restriction of 60 seconds and the number of steps per loop between 10,000-1,000,000. The below figure shows the resulting solution for problem G65.

The numbers written next to data points indicate the number of loops that the SBM was able to execute within the time limit of 60 seconds.

For problem G65, setting the amount of steps to values greater than 500,000 results in more optimal solutions than running many loops with less steps.

Whether a large number of short loops or a small number of long loops is preferable seems to depend on the problem at hand. Thus, finding an appropriate number for steps is key for efficient solving.

Conclusion

Using the SBM, we were able to find approximate solutions to MAX-CUT problems at high speed. In particular comparatively small problems with about 2000 vertices were largely solved in less than a second.

Among the Ising formulated problems, MAX-CUT problems are considered relatively easy to solve since they have no constraints. While we have treated MAX-CUT problems from the Gset dataset for this benchmark, we intend to do similar tests with more complicated and realistic optimization problems. Through further tuning, we will also investigate how much more speed and precision can be achieved with the SBM.