# Benchmarking the MAX-CUT problem on the Simulated Bifurcation Machine

# 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

`5 7`

1 2 1

1 5 1

2 3 -1

2 4 1

2 5 -1

3 4 -1

4 5 1

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.