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$ と整数 $K$ が与えられたとき、$G$ の頂点を $K$ 色で塗り分けて、同じ色の頂点のペアがすべて辺で結ばれているようにできるかどうか判定する問題を クリーク被覆問題 といいます。
たとえば、以下のようなグラフは、3 つの青色の頂点はすべて辺で結ばれていて、3 つのオレンジ色の頂点もすべて辺で結ばれているので、$G$ を $2$ つのクリークで被覆することは可能だということになります。
ここでは、Fixstars Amplify を用いて、このような頂点の塗り分け方を探索するプログラムを作成します。定式化は A. Lucas, Front. Phys. (2014) の 6.2 節のものに沿って行います。
問題の作成¶
まず、例題として、NetworkX を用いて適当なグラフ $G$ を作成します。また、今回は、色の数 $K$ を $2$ とします。
import networkx as nx
N = 6 # グラフの頂点数
K = 2 # 色の数
G = nx.Graph()
G.add_nodes_from(range(N))
edge_list = [
(0, 1),
(0, 2),
(1, 2),
(1, 3),
(1, 4),
(2, 3),
(2, 5),
(3, 4),
(3, 5),
(4, 5),
]
G.add_edges_from(edge_list)
pos = nx.spring_layout(G, seed=0)
nx.draw_networkx(G, node_size=600, font_color="w", pos=pos)
作成したグラフは、最初に示したものと同じグラフとなっています。したがって、頂点 $0$, $1$, $2$ を片方の色で、頂点 $3$, $4$, $5$ をもう片方の色で塗れば条件をみたす塗り方となります。
定式化¶
以下、$G$ の頂点の数を $N$ とします。
決定変巣¶
$N \times K$ のバイナリ決定変数テーブル $q$ を作成し、それぞれの頂点をどの色で塗るかを表します。頂点 $i$ が $j$ 番目の色で塗られるとき、$q$ の $i$ 行 $j$ 列にあるバイナリ変数が $1$ となります。
たとえば、頂点 $0$, $1$, $2$ を $0$ 番目の色で塗り、頂点 $3$, $4$, $5$ を $1$ 番目の色で塗るとき、変数テーブル $q$ は以下のようになります。
| $q$ | 0 番目の色 | 1 番目の色 |
|---|---|---|
| 頂点 0 | 1 | 0 |
| 頂点 1 | 1 | 0 |
| 頂点 2 | 1 | 0 |
| 頂点 3 | 0 | 1 |
| 頂点 4 | 0 | 1 |
| 頂点 5 | 0 | 1 |
目的関数¶
クリーク被覆問題は条件を満たすものを 1 つ見つける問題なので、目的関数は $0$（無し）とします。
制約条件¶
$q$ と対応する塗り分け方によって、$G$ が $K$ 個のクリークで被覆されるためには、以下が必要です。
- 条件 1 ： $G$ の各頂点は、ちょうど $1$ つの色で塗られている。
- 条件 2 ： 同じ色の頂点は、必ず辺で結ばれている。
条件 1 は、各行に $1$ つだけ $1$ があるという制約であり、数式で表すと
$$ \sum_{j = 0}^{K-1} q_{i, j} = 1 \quad \text{for} \quad i \in \{0, 1, \ldots, N-1\} $$
となります。
また、条件 2 を、対偶をとって「辺で結ばれていない $2$ 頂点は、同じ色では塗られていない」と言い換えると、これは
$$ q_{u, j} q_{v, j} = 0 \quad \text{for} \quad (u, v) \notin E, \ j \in \{0, 1, \ldots, K - 1\} $$
で表せます。ただし、$E$ は $G$ の辺集合です。
実装¶
上で作成した問題と定式化を使って、実際に問題を解いてみましょう。最初に、Fixstars Amplify SDK の BinarySymbolGenerator を使って
$N\times K$ 個のバイナリ変数 $q$ を作成します。
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, K))
次に、条件 1 に対応する制約条件を作成します。条件 1 は、$q$ の各行にひとつだけ 1 があるという条件でしたので、one_hot
を使って書くことができます。二次元配列の各行に対する one-hot 制約を一度に生成するには、axis パラメータに 1 を指定すればよいです。
from amplify import one_hot
constraint1 = one_hot(q, axis=1)
条件 2 に対応する制約条件を作成します。条件 2 は、 $q_{u, j} q_{v, j} = 0 \ \bigl((u, v) \notin E, \ j \in \{0, 1, \ldots, K - 1\}\bigr)$ という条件でした。
from amplify import equal_to, sum as amplify_sum
constraint2 = amplify_sum(
equal_to(q[u, j] * q[v, j], 0) for (u, v) in nx.non_edges(G) for j in range(K)
)
作成した制約条件をまとめて、組合せ最適化モデルを構築します。
from amplify import Model
model = Model(constraint1 + constraint2)
クライアントを設定し、Fixstars Amplify Annealing Engine (AE) で実行します。
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)
解が見つかったかどうかを確認します。Amplify SDK は制約条件をみたす解を自動でフィルターするので、result
が空でなければ、制約条件をみたす解が見つかったと分かります。
if len(result) == 0:
print("解が見つかりませんでした。")
else:
print("解が見つかりました。")
最後に、結果を可視化します。
import numpy as np
values = q.evaluate(result.best.values)
colors = [f"C{i}" for i in np.where(values == 1)[1]]
nx.draw_networkx(G, node_size=600, node_color=colors, font_color="w", pos=pos)
