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$ 色で塗り分けて、辺で結ばれている頂点同士が同じ色にならないようにできるかどうかを判定する問題を グラフ彩色問題 といいます。
たとえば、以下の図では、$G$ の頂点は青色、オレンジ色、灰色の $3$ 色のいずれかで塗られていて、どの辺についても 2 つの端点は異なる色となっています。
本サンプルプログラムでは、Fixstars Amplify を用いて頂点の塗り分け方を探索するプログラムを作成します。定式化は A. Lucas, Front. Phys. (2014) の 6.1 節のものに沿って行います。
問題の作成¶
まず、例題として、NetworkX を用いて適当なグラフ $G$ を作成します。また、色の数 $K$ は $3$ としておきます。
import networkx as nx
K = 3 # 色の数
N = 6 # グラフの頂点数
G = nx.Graph()
G.add_nodes_from(range(N))
edge_list = [(0, 1), (0, 2), (0, 4), (0, 5), (1, 2), (1, 5), (2, 3), (3, 4), (4, 5)]
G.add_edges_from(edge_list)
pos = nx.circular_layout(G)
nx.draw_networkx(G, node_size=600, font_color="w", pos=pos)
定式化¶
以下、グラフ $G$ の頂点の数を $N$ とします。また、色の数は $K$ であったことを思い出しておきましょう。
決定変数¶
$N \times K$ のバイナリ決定変数テーブル $q$ を用意し、それぞれの頂点をどの色で塗るかを 0, 1 で表すことにします。つまり、頂点 $v$ を 色 $k$ で塗るとき、$q_{v, k} = 1$ とします。
たとえば、以下のように頂点を塗るとき、対応するバイナリ変数テーブル $q$ は下の表のようになります。
| 頂点 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 色 | 0 | 1 | 2 | 0 | 1 | 2 |
| $q$ | 色 0 | 色 1 | 色 2 |
|---|---|---|---|
| 頂点 0 | 1 | 0 | 0 |
| 頂点 1 | 0 | 1 | 0 |
| 頂点 2 | 0 | 0 | 1 |
| 頂点 3 | 1 | 0 | 0 |
| 頂点 4 | 0 | 1 | 0 |
| 頂点 5 | 0 | 0 | 1 |
目的関数¶
この問題は条件をみたす解を 1 つ見つければよいので、目的関数は $0$ （無し）で良いです。
制約条件¶
$q$ が塗り分けのルールをみたす塗り方と対応するには、以下の条件を満たす必要があります。
- 条件 1 ：各頂点はちょうど 1 色で塗られている。つまり、$q$ の各行には $1$ が 1 つだけある。
- 条件 2 ：辺で結ばれている 2 頂点は、同じ色で塗られていない。
条件 1 は、$q$ の各行に関する one-hot 制約ですので、
$$ \sum_{k = 0}^{K - 1} q_{v, k} = 1 \quad\text{for}\quad v \in V $$
で表せます。ここで、$V$ は $G$ の頂点集合です。
条件 2 は、$G$ の辺 $E$ を構成する 2 頂点 $(u, v)$ の色が異なるということであり、
$$ q_{u, k} q_{v, k} = 0 \quad\text{for}\quad (u, v) \in E, \ k \in \{0, 1, \ldots, K-1\} $$
で表せます。ここで、$E$ は $G$ の辺集合です。
$q$ が条件 1 と条件 2 をみたしていれば、$q$ は条件をみたす塗り分け方に対応します。
実装¶
上で作成した問題と定式化を使って、実際に問題を解いてみましょう。最初に、Fixstars Amplify SDK の BinarySymbolGenerator を使って
$N\times K$ 個のバイナリ変数 $q$ を作成します。
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, K))
条件 1 に対応する制約条件を作成します。条件 1 の、$q$ の各行に関する one-hot 制約は、one-hot 関数の axis パラメータに
1
を指定することで実装できます。
from amplify import one_hot
constraint1 = one_hot(q, axis=1)
条件 2 に対応する制約条件を作成します。条件 2 は、辺で結ばれた 2 頂点は異なる色で塗られていることであり、 $q_{u, k} q_{v, k} = 0 \ \bigr((u, v) \in E, \ k \in \{0, 1, \ldots, K-1\}\bigl)$ で表されます。次のように実装できます。
from amplify import equal_to, sum as amplify_sum
constraint2 = amplify_sum(
equal_to(q[u, k] * q[v, k], 0) for (u, v) in G.edges for k 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
color_list = ["C0", "C1", "C7"]
values = q.evaluate(result.best.values)
colors = [color_list[k] for k in np.where(values == 1)[1]]
nx.draw_networkx(G, node_size=600, font_color="w", node_color=colors, pos=pos)
