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節）
厳密被覆問題とは¶
集合 $S$ があり、$S$ の部分集合 $T_0, T_1, \ldots, T_{N-1}$ が与えられているとします。 $T_0, T_1, \dots, T_{N-1}$ の中からいくつかを選び、選んだ複数の部分集合が $S$ の分割となるようにすることができるかどうか判定する問題を 厳密被覆問題 といいます。つまり、$S$ のどの要素も、選んだ部分集合のうちちょうど 1 つに含まれているようにできるかどうかを判定します。
たとえば、下図のように $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ のとき、部分集合として、$T_0 = \{1, 2, 3, 6, 9\}$、 $T_1 = \{1, 2, 5, 8\}$、 $T_2 = \{4, 7\}$、 $T_3 = \{4, 5\}$、 $T_4 = \{6, 9\}$、 $T_5 = \{3\}$ とすることを考えます。このとき、$T_1$、$T_2$、$T_4$、$T_5$ を選ぶとこれらは $S$ の分割となります。
ここでは、Fixstars Amplify を用いて厳密被覆問題を解くプログラムを作成します。定式化は A. Lucas, Front. Phys. (2014) の 4.1 節のものに沿って行います。
問題の作成¶
例題として、上に挙げた問題をコードで表現しておきます。
S = [1, 2, 3, 4, 5, 6, 7, 8, 9] # 集合 S
T = [[1, 2, 3, 6, 9], [1, 2, 5, 8], [4, 7], [4, 5], [6, 9], [3]] # Sの複数の部分集合
定式化¶
決定変数¶
$N$ 個のバイナリ変数 $q$ を $T_0, T_1, \ldots, T_{N-1}$ と対応付けて、対応する部分集合 $T_i$ を選ぶかどうかを表すことにします。$T_i$ を選ぶ場合、$q_i$ は $1$ で、選ばない場合は $0$ です。
たとえば、$T_1$, $T_2$, $T_4$, $T_5$ の 4 つの部分集合を選ぶときは、$q$ は以下のようになります。
| 部分集合 | $$T_0$$ | $$T_1$$ | $$T_2$$ | $$T_3$$ | $$T_4$$ | $$T_5$$ |
|---|---|---|---|---|---|---|
| $$q$$ | 0 | 1 | 1 | 0 | 1 | 1 |
目的関数¶
この問題は条件を満たす解を 1 つ見つける問題なので、目的関数は $0$（考慮しない）となります。今回は実装しませんが、この問題の発展バージョンとして、選ぶ部分集合の個数をできるだけ小さくしたい場合は、最適化問題となるため、目的関数として $\displaystyle \sum_{i = 0}^{N-1} q_i$ を設定する必要があります。
制約条件¶
「どの $S$ の要素も、選んだ部分集合のうちちょうど $1$ つに含まれる」という条件は、 「どの $S$ の要素 $x$ に対しても、$x$ を含む部分集合 $T_i$ のうちちょうど $1$ つが選ばれる」 と言い換えることができます。これは、
$$ \sum_{T_i \ni x} q_i = 1 \quad \text{for} \quad x \in S $$
で表せます。
実装¶
上で作成した問題と定式化を使って、実際に問題を解いてみましょう。最初に、Fixstars Amplify SDK の BinarySymbolGenerator
を使って部分集合の数だけバイナリ変数 $q$ を作成します。
from amplify import VariableGenerator
N = len(T) # 部分集合の数
gen = VariableGenerator()
q = gen.array("Binary", N)
次に、制約条件を構築します。前述の通り、$S$ の各要素 $x$ に対して、$x$ を含む部分集合のうちちょうど 1 つが選ばれるという制約条件を満たす必要があります。
from amplify import one_hot, sum as amplify_sum
constraints = amplify_sum(
one_hot(amplify_sum(q[i] for i in range(N) if x in T[i])) for x in S
)
作成した制約条件から組合せ最適化モデルを構築します。
from amplify import Model
model = Model(constraints)
クライアントを設定して、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("解が見つかりました")
最後に、結果を可視化します。余裕があれば、集合 $S$ やその部分集合 $T_i$ を変更して、厳密被覆が可能か試してみましょう。
import numpy as np
values = q.evaluate(result.best.values)
for i in np.where(values == 1)[0]:
print(f"T{i} : {T[i]}")
