A. Lucas, Front. Phys. (2014) 掲載例題の実装と解説 ー グラフの分割問題¶
本サンプルコードでは、論文 A. Lucas, "Ising formulations of many NP problems", Front. Phys. (2014) で紹介されている『グラフの分割問題』に Fixstars Amplify を用いて取り組みます。同論文に紹介されている他の NP 完全・NP 困難な問題も以下で解説しています（カッコ内は論文内で問題に対応する節番号）。
- グラフの分割問題（2.2節）
- 最大クリーク問題（2.3節）
- 厳密被覆問題（4.1節）
- 集合パッキング問題（4.2節）
- 最小頂点被覆問題（4.3節）
- 充足可能性問題（SAT）（4.4節）
- 最小極大マッチング問題（4.5節）
- グラフ彩色問題（6.1節）
- クリーク被覆問題（6.2節）
- 整数長ジョブスケジューリング問題（6.3節）
- ハミルトン閉路問題（7.1節）
- 有向帰還頂点集合問題（8.3節）
- 最小帰還辺集合問題（8.5節）
- グラフ同型性判定問題（9節）
グラフ分割問題とは¶
$2N$ 個の頂点からなるグラフ $G$ があるとします。$G$ の頂点を $N$ 個ずつ 2 つの集合に分割する方法のうち、異なる集合に属する $2$ 点を結ぶ $G$ の辺の数が最小となるようなものを求める問題を グラフ分割問題 といいます。
たとえば、以下のようなグラフにおいて、8 つの頂点をオレンジ色の 4 頂点の集合と青色の 4 頂点の集合に分割すると、青い頂点とオレンジ色の頂点を結ぶ辺は 2 本です。また、この分割の仕方が最適解であることも簡単に分かります。
グラフ分割問題のより詳細な解説はこちらをご覧ください。
本サンプルプログラムでは、Fixstars Amplify を用いてグラフ分割問題を解くプログラムを作成します。定式化は A. Lucas, Front. Phys. (2014) の 2.2 節のものに沿って行います。
問題の作成¶
まず、例題として、NetworkX を用いて $2N$ 個の頂点を有するグラフ $G$ を作成します。
import networkx as nx
N = 4 # グラフの頂点数の半分
G = nx.Graph()
G.add_nodes_from(range(2 * N))
# 2つの頂点をつなぐ辺を定義
edge_list = [
(0, 1),
(0, 2),
(1, 2),
(2, 3),
(3, 4),
(3, 5),
(3, 6),
(4, 5),
(5, 6),
(6, 7),
]
G.add_edges_from(edge_list)
pos = nx.circular_layout(G)
nx.draw_networkx(G, node_size=300, font_color="w", pos=pos)
定式化¶
決定変数¶
グラフ $G$ の頂点数に等しい $2N$ 個のバイナリ変数 $q$ を $G$ の各頂点と対応させて、それぞれの頂点がどちらの集合に属するかを表すことにします。例えば、$q=0$ を青で示された頂点グループ、$q=1$ をオレンジで示された頂点グループとすると、以下のような分割の仕方に対応するバイナリ変数の組み合わせは下の表のようになります。
| 頂点のインデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| $q$ | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
目的関数¶
グラフの分割問題を解くには、異なる集合に属する頂点同士を結ぶ辺の数を最小化するように決定変数 $q$ の値を決定すればよいです。
$G$ の頂点 $u$ と $v$ が異なる集合に属するには $q_u$ と $q_v$ の排他的論理和 (xor) が 1 になればよく、これは 2 次式で書くと $-2q_u q_v + q_u + q_v$ で表されます。辺で結ばれている頂点の組 $(u, v)$ すべてのうち、$u$ と $v$ が異なる集合に属するものの数が最小となればよいので、目的関数は
$$ \sum_{(u, v) \in E} \operatorname{xor}(q_u, q_v) = \sum_{(u, v) \in E} -2q_uq_v + q_u + q_v $$
で表すことができます。
制約条件¶
決定変数 $q$ が表す $G$ の頂点集合の分割が、頂点 $N$ 個からなる 2 つの集合への分割になっているためには、 $0$ となるバイナリ変数と $1$ となるバイナリ変数がそれぞれ $N$ 個ずつであることが必要十分です。 これは、
$$ \sum_{i = 0}^{2N-1}q_i = N $$
で表すことができます。
実装¶
上で作成した問題と定式化を使って、実際に問題を解いてみましょう。最初に、Fixstars Amplify SDK の BinarySymbolGenerator
を使ってバイナリ変数
$q$ を作成します。
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", 2 * N)
次に、目的関数 $\sum_{(u, v) \in E} \operatorname{xor}(q_u, q_v)$ を作成します。Fixstars Amplify
のバイナリ変数には論理演算子がオーバーロードされていて、q[u] ^ q[v] で $\operatorname{xor}(q_u, q_v)$ と同じ値をとる 2
次多項式（$-2q_uq_v + q_u + q_v$）を計算することができます。
from amplify import sum
cost = sum([q[u] ^ q[v] for u, v in G.edges])
続いて、制約条件を作成します。前述の通り、制約条件は、$2N$ 個のバイナリ変数の和がちょうど $N$ になるという条件です。
from amplify import equal_to
constraint = equal_to(q, N)
作成した目的関数と制約条件をまとめて組合せ最適化モデルを構築します。
model = cost + constraint
クライアントを設定して、Fixstars Amplify Annealing Engine (AE) で実行します。Amplify SDK
は制約条件をみたす解を自動でフィルターするので、result が空でなければ、制約条件をみたす解が見つかったと分かります。
from amplify import FixstarsClient, solve
from datetime import timedelta
client = FixstarsClient()
client.parameters.timeout = timedelta(milliseconds=1000) # タイムアウトは 1000 ms
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境等で使用する場合は、Fixstars Amplify AE のアクセストークンを入力してください。
# 構築した model に対して求解を実行
result = solve(model, client)
if len(result) == 0:
print("解が見つかりませんでした。")
else:
print("解が見つかりました。")
最後に、得られたグラフの分割を可視化します。上記で示したグラフと同様な問題設定ですので、得られる分割も同様となっています。余裕があれば、グラフの形状や辺の数を変更して、分割できるか試してみましょう。
values = q.evaluate(result.best.values)
colors = [f"C{int(value)}" for value in values]
nx.draw_networkx(G, node_size=600, node_color=colors, font_color="w", pos=pos)
