Max-Cut Problem¶

The Max-Cut problem is one of the most well-known combinatorial optimization problems. In this tutorial, we will walk through the problem definition and solve it using the Amplify SDK.

1. Problem Definition and Ising Variables¶

The Max-Cut problem aims to partition the vertex set \(V\) of a graph \(G=(V, E)\) into two subsets \(V_1\) and \(V_2\) such that the total weight of edges crossing the partition is maximized.

Representing the Partition with Ising Variables¶

To represent which subset each vertex \(i \in V\) belongs to, we introduce an Ising variable \(s_i \in \{-1, +1\}\).

If \(s_i = +1\), vertex \(i\) belongs to subset \(V_1\)
If \(s_i = -1\), vertex \(i\) belongs to subset \(V_2\)

Expressing the Cut Condition¶

An edge \((i, j) \in E\) is cut when vertices \(i\) and \(j\) belong to different subsets, that is, when \(s_i\) and \(s_j\) have different values (\(s_i s_j = -1\)). Consider the expression \(\left(1 - s_i s_j\right)/2\):

\(s_i\)	\(s_j\)	\(s_i s_j\)	\(\left(1 - s_i s_j\right)/2\)	Cut status
+1	+1	+1	0	Not cut
-1	-1	+1	0	Not cut
+1	-1	-1	1	Cut
-1	+1	-1	1	Cut

This expression takes the value 1 when the edge is cut and 0 otherwise, making it directly usable in the objective function.

2. Formulation¶

Objective Function (Maximization)¶

Let \(w_{ij}\) denote the weight of edge \((i, j)\). The Max-Cut problem can be formulated as the following maximization problem:

\[ \text{maximize} \quad J(s) = \sum_{(i, j) \in E} w_{ij} \left( \frac{1 - s_i s_j}{2} \right) \]

Objective Function (Minimization / Ising Form)¶

Since the Amplify SDK minimizes the energy, we drop the constant term and minimize the following Ising Hamiltonian:

\[ \text{minimize} \quad H(s) = \sum_{(i, j) \in E} w_{ij} s_i s_j \]

Problem Setup¶

Consider the following graph with 4 vertices \(\{0, 1, 2, 3\}\) where all edge weights are 1.0.

maxcut_problem

We define the weight matrix as the adjacency matrix of the graph. Vertices 0-1, 1-2, 2-3, and 3-0 are connected by edges, all with weight 1.0.

import numpy as np

weights = np.array([
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0],
])

Formulation with the Amplify SDK¶

Creating Variables¶

We create Ising variables \(s_0, s_1, s_2, s_3\) corresponding to each vertex. Ising variables take values in \(\{-1, +1\}\) and can be created in the Amplify SDK by specifying "Ising".

from amplify import VariableGenerator

gen = VariableGenerator()
s = gen.array("Ising", 4)

s

\[\displaystyle [s_0, s_1, s_2, s_3]\]

Creating the Objective Function¶

We construct the objective function \(H(s) = \sum_{(i, j) \in E} w_{ij} s_i s_j\) using einsum.

from amplify import einsum

objective = einsum("i,j,ij->", s, s, weights)

print(objective)

2 s_0 s_1 + 2 s_0 s_3 + 2 s_1 s_2 + 2 s_2 s_3

Using the objective function we created, we build a combinatorial optimization model.

from amplify import Model

model = Model(objective)

print(model)

minimize:
  2 s_0 s_1 + 2 s_0 s_3 + 2 s_1 s_2 + 2 s_2 s_3

Setting Up the Solver¶

We create a solver client and configure the solver parameters. In this example, we use Amplify AE.

from amplify import AmplifyAEClient

client = AmplifyAEClient()

We set the API token required to run the solver and configure the solver parameters.

from datetime import timedelta

client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)

from datetime import timedelta

client.token = ""
client.parameters.time_limit_ms = timedelta(milliseconds=1000)

Solving with the Amplify SDK¶

We execute the solver using the combinatorial optimization model and solver client created above.

from amplify import solve

result = solve(model, client)

Checking the Results¶

The values of the variables \(s = (s_0, s_1, s_2, s_3)\) can be obtained as follows.

s_values = s.evaluate(result.best.values)

print(f"objective: {result.best.objective}")
print(f"solution:  {s_values}")

objective: -8.0
solution:  [-1.  1. -1.  1.]

The solution \([-1, 1, -1, 1]\) or \([1, -1, 1, -1]\) is obtained. These two solutions differ only by an overall sign flip and represent the same cut structure. Both correspond to the partition into \(\{0, 2\}\) and \(\{1, 3\}\), as shown in the figure below.

maxcut_answer

Vertices 0 and 2 are placed in one group, and vertices 1 and 3 in the other, maximizing the total weight of cut edges.