Max-Cut (最大カット) 問題¶
Max-Cut (最大カット) 問題は、代表的な組合せ最適化問題の一つです。ここでは、問題の定義から、Amplify SDK を用いた求解までを解説します。
1. 問題の定義とイジング変数¶
Max-Cut 問題は、グラフ \(G=(V, E)\) の頂点集合 \(V\) を二つの部分集合 \(V_1\) と \(V_2\) に分割し、カットされる辺の重みの総和を最大化することを目的とします。
イジング変数による分割の表現¶
各頂点 \(i \in V\) がどちらの集合に属するかを表すために、イジング変数 \(s_i \in \{-1, +1\}\) を導入します。
\(s_i = +1\) の場合、頂点 \(i\) は集合 \(V_1\) に属する
\(s_i = -1\) の場合、頂点 \(i\) は集合 \(V_2\) に属する
カット条件の表現¶
辺 \((i, j) \in E\) がカットされるのは、頂点 \(i\) と \(j\) が異なる集合に属するとき、すなわち \(s_i\) と \(s_j\) の値が異なる場合 (\(s_i s_j = -1\)) です。 ここで、項 \(\left(1 - s_i s_j\right)/2\) を考えると、以下のようになります。
\(s_i\) |
\(s_j\) |
\(s_i s_j\) |
\(\left(1 - s_i s_j\right)/2\) |
意味 (カット) |
|---|---|---|---|---|
+1 |
+1 |
+1 |
0 |
カットされない |
-1 |
-1 |
+1 |
0 |
カットされない |
+1 |
-1 |
-1 |
1 |
カットされる |
-1 |
+1 |
-1 |
1 |
カットされる |
この項は辺がカットされた場合に 1、カットされない場合に 0 を取り、そのまま目的関数に利用できます。
2. 定式化¶
目的関数 (最大化)¶
辺 \((i, j)\) の重みを \(w_{ij}\) とすると、Max-Cut 問題は以下の最大化問題として定式化されます。
目的関数 (最小化 / Ising 形式)¶
Amplify SDK はエネルギーを最小化するため、定数項を除いた以下のイジングハミルトニアンの最小化として扱います。
問題の作成¶
4 つの頂点 \(\{0, 1, 2, 3\}\) を持ち、辺の重みが全て 1.0 の以下のグラフを考えます。
グラフの隣接行列を重み行列として定義します。頂点 0-1, 1-2, 2-3, 3-0 が辺で結ばれており、重みは全て 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],
])
Amplify SDK による定式化¶
変数の生成¶
各頂点に対応するイジング変数 \(s_0, s_1, s_2, s_3\) を作成します。イジング変数は \(\{-1, +1\}\) の値をとる変数で、Amplify SDK では "Ising" を指定することで作成できます。
from amplify import VariableGenerator
gen = VariableGenerator()
s = gen.array("Ising", 4)
s
目的関数の作成¶
目的関数 \(H(s) = \sum_{(i, j) \in E} w_{ij} s_i s_j\) を 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
作成した目的関数を使って、組合せ最適化モデルを構築します。
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
ソルバーの設定¶
ソルバークライアントを作成し、求解を行うためのソルバーの指定およびパラメータの設定を行います。本サンプルコードでは Amplify AE を使用します。
from amplify import AmplifyAEClient
client = AmplifyAEClient()
ソルバーで求解を行うために必要なトークンと、ソルバーのパラメータを設定します。
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)
Amplify SDK による求解¶
上記で作成した組合せ最適化モデルとソルバークライアントを使用して、求解を実行します。
from amplify import solve
result = solve(model, client)
結果の確認¶
変数 \(s = (s_0, s_1, s_2, s_3)\) の値は、以下のように得ることができます。
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.]
解 \([-1, 1, -1, 1]\) または \([1, -1, 1, -1]\) が得られます。これらは全体の符号が反転しただけで同じカット構造を表しています。いずれも頂点 \(\{0, 2\}\) と \(\{1, 3\}\) への分割に対応し、以下の図のようになります。
頂点 0 と 2 が一方のグループに、頂点 1 と 3 がもう一方のグループに分割されることで、カットされる辺の重みの総和が最大化されます。