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節）
最大クリーク問題とは¶
グラフ $G$ に対して、$G$ の頂点の部分集合であって、それに含まれるどの $2$ 頂点も辺で結ばれているもの (クリークといいます) のうち、要素数が最も大きいものを求める問題を 最大クリーク問題 といいます。
たとえば、以下のグラフのオレンジ色の頂点同士はすべて辺で結ばれているので、オレンジ色の 4 頂点はクリークをなします。 また、次数（頂点から出ている辺の数）が 4 以上の頂点が 3 つしかないことから、 5 点からなるクリークが存在しないことも分かります。
最大クリーク問題のより詳細な解説はこちらをご覧ください。
本サンプルプログラムでは、Fixstars Amplify を用いて最大クリークを探索するプログラムを作成します。定式化は A. Lucas, Front. Phys. (2014) の 2.3 節のものに沿って行います。
問題の作成¶
最大クリーク問題を解くための準備として、NetworkX を用いて適当なグラフ $G$ を作成します。
import networkx as nx
N = 7 # グラフの頂点数
G = nx.Graph()
G.add_nodes_from(range(N))
# 2つの頂点をつなぐ辺を定義
edge_list = [
(0, 1),
(0, 6),
(1, 2),
(1, 3),
(1, 4),
(1, 6),
(2, 3),
(3, 4),
(3, 5),
(3, 6),
(4, 6),
(5, 6),
]
G.add_edges_from(edge_list)
pos = nx.circular_layout(G)
nx.draw_networkx(G, node_size=600, font_color="w", pos=pos)
作成したグラフは、最初に例として挙げたグラフと同じものなので、前述の通りクリークの最大の要素数は 4 となります。
定式化¶
以下、$G$ の頂点の数を $N$ とします。
決定変数¶
グラフ $G$ の頂点数に等しい $N$ 個のバイナリ変数 $q$ をそれぞれの頂点に対応させて、クリークに含まれるかどうかを表すことにします。頂点 $i$ がクリークに含まれるならば $q_i$ は $1$ で、含まれないならば $0$ です。
たとえば、以下の図のように頂点 1、頂点 3、頂点 4、頂点 6 からなるクリークは、下の表のように表されます。
| 頂点インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| $q$ | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
目的関数¶
クリークのサイズができるだけ大きければよいので、目的関数は
$$ -\sum_{i = 0}^{N - 1} q_i $$
となります。マイナスがついているのは、最大化問題を最小化問題にするためです。
制約条件¶
バイナリ変数 $q$ がクリークに対応するためには、「クリークに含まれる各頂点はすべて辺で結ばれている」という制約を課す必要があります。この対偶をとると「頂点 $u$, $v$ が辺で結ばれていないとき、$u$ と $v$ の少なくともどちらかはクリークに含まれない」という条件に言い換えられます。この条件は
$$ q_uq_v = 0 \quad\text{for}\quad (u, v) \notin E $$
で表すことができます。ここで、$E$ は $G$ の辺集合です。
実装¶
上で作成した問題と定式化を使って、実際に問題を解いてみましょう。まず、Fixstars Amplify SDK の BinarySymbolGenerator
を使ってバイナリ変数
$q$ を作成します。
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", N)
目的関数を作成します。先に紹介した通り、目的関数はクリークに含まれる頂点の数の $-1$ 倍と等しく、$-\sum_{i=0}^{N-1}q_i$ で表されます。
cost = -q.sum()
次に、制約条件を作成します。前述の通り、制約条件は、クリークに含まれる頂点はすべて辺で結ばれているという条件と等価であり、その対偶 $q_uq_v = 0 \ \left( (u, v) \notin E\right)$ で表すことができます。
from amplify import equal_to, sum as amplify_sum
constraints = amplify_sum(equal_to(q[u] * q[v], 0) for u, v in nx.non_edges(G))
目的関数と制約条件をまとめて組合せ最適化モデルを構築します。
model = cost + constraints
クライアントを設定して、Fixstars Amplify Annealing Engine (AE) で実行します。Amplify SDK
は制約条件をみたす解を自動でフィルターするので、result が空でなければ、制約条件をみたす解が見つかったと分かります。
from amplify import FixstarsClient, solve
from datetime import timedelta
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境等で使用する場合は、Fixstars Amplify AE のアクセストークンを入力してください。
client.parameters.timeout = timedelta(milliseconds=1000) # タイムアウトは 1000 ms
# 求解を実行
result = solve(model, client)
if len(result) == 0:
print("解が見つかりませんでした")
else:
print("解が見つかりました")
最後に、結果を可視化します。上記で示したグラフと同様な問題設定ですので、得られる最大クリークも同じものが求解されています。余裕があれば、グラフの形状や辺の数を変更して、最大クリークが求まるか試してみましょう。
values = q.evaluate(result.best.values)
colors = ["C1" if value == 1 else "C0" for value in values]
nx.draw_networkx(G, node_size=600, node_color=colors, font_color="w", pos=pos)
