厳密被覆問題

厳密被覆問題#

ここでは、JijSolverとJijModelingを用いて、厳密被覆問題を解く方法を紹介します。この問題はLucas, 2014, “Ising formulations of many NP problems” 4.1. Exact Coverでも触れられています。

厳密被覆問題とは#

集合\(U = \{1, \dots, M\}\)と、その部分集合\(W_i \subseteq U \ (i = 1, \dots, N)\)を考えましょう。すなわち

\[ U = \bigcup_i W_i \]

が成り立つとします。このとき、厳密被覆問題とは、「\(W_i\)に含まれる部分集合\(R\)において、\(R\)の要素が重複することなく、その要素の和が集合\(U\)を構成するような\(R\)は存在するか？」を求める問題です。

具体例#

例として、次の場合について考えましょう。集合\(U\)は\(\{1, 2, 3, 4, 5, 6, 7\}\)の要素を持つとし、\(W_i\)は以下のように\(U\)の部分集合からなるものとします。

\[\begin{split} \begin{align} &W_1 = \{1, 2, 3\}, \\ &W_2 = \{4, 5\},\\ &W_3 = \{6, 7\},\\ &W_4 = \{3, 5, 7\},\\ &W_5 = \{2, 5, 7\},\\ &W_6 = \{3, 6, 7\}. \end{align} \end{split}\]

\(R\)の要素に重複はなく、その和がちょうど\(U\)に一致するような\(W_i\)の部分集合\(R\)が存在するかを考えると、この例題では

\[ R = \{W_1, W_2, W_3\}. \]

が厳密解となります。

数理モデル#

\(W_i\)を選ぶとき1、そうでないとき0となるようなバイナリ変数\(x_i\)を用います。

制約: \(U\)の各要素は、選ばれた部分集合の中に一度だけ現れなければならない

この制約は、次のように表現されます。

\[ \sum_{i=1}^N x_i \cdot V_{i, j} = 1 \text{ for } j = 1, \ldots, M \tag{1} \]

ここで、\(V_{i, j}\)は\(i\)番目の部分集合から\(j\)番目の要素へのマップを表します。具体的には、\(V_{i, j}\)が1のときは\(W_i\)が要素\(j\)を含み、そうでないときは0となります。先程の例の場合には、次のように列挙することができます。

\[\begin{split} \begin{align} &x_1 = 1 \because 1 \text{ appears only in } W_1, \\ &x_1 + x_5 = 1 \because 2 \text{ appears in } W_1 \text{ and } W_5, \\ &x_1 + x_4 + x_6 = 1 \because 3 \text{ appears in } W_1, W_4, \text{ and } W_6, \\ &x_2 = 1 \because 4 \text{ appears only in } W_2, \\ &x_2 + x_4 + x_5 = 1 \because 5 \text{ appears in } W_2, W_4, \text{ and } W_5, \\ &x_3 + x_6 = 1 \because 6 \text{ appears in } W_3 \text{ and } W_6, \\ &x_3 + x_4 + x_5 + x_6 = 1 \because 7 \text{ appears in } W_3, W_4, W_5, \text{ and } W_6 . \end{align} \end{split}\]

目的関数: 選択する集合数を最小にする

これは、次のように表現されます。

\[ \min \sum_i x_i \tag{2} \]

JijModelingによるモデル化#

次に、JijModelingを用いた実装を示します。最初に、上述の数理モデルで用いた変数を定義します。

import jijmodeling as jm

# define variables
U = jm.Placeholder('U')
N = jm.Placeholder('N')
M = jm.Placeholder('M')
V = jm.Placeholder('V', ndim=2)
x = jm.BinaryVar('x', shape=(N,))
i = jm.Element('i', N)
j = jm.Element('j', M)

Uは被覆したい集合、Nは部分集合の数、Mは要素数、Vは部分集合\(i\)が要素\(j\)を含んでいるかどうかを表します。 2次元のバイナリ変数列をxとして定義し、最後に数理モデルで用いた添字をi, jとして定義しています。

制約#

式(1)の制約を実装しましょう。

# set problem
problem = jm.Problem('Exact Cover')
# set constraint: each element j must be in exactly one subset i
problem += jm.Constraint('onehot', jm.sum(i, x[i]*V[i, j]) == 1, forall=j)

目的関数#

次は目的関数の実装です。

problem += jm.sum(i, x[i])

実装した数理モデルを、Jupyter Notebookで表示してみましょう。

problem

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{Exact Cover} & & \\& & \min \quad \displaystyle \sum_{i = 0}^{N - 1} x_{i} & \\\text{{s.t.}} & & & \\ & \text{onehot} & \displaystyle \sum_{i = 0}^{N - 1} x_{i} \cdot V_{i, j} = 1 & \forall j \in \left\{0,\ldots,M - 1\right\} \\\text{{where}} & & & \\& x & 1\text{-dim binary variable}\\\end{array}\end{split}\]

インスタンスの準備#

先程の例題と同じものを準備しましょう。

import numpy as np

# set a list of W
W_1 = [1, 2, 3]
W_2 = [4, 5]
W_3 = [6, 7]
W_4 = [3, 5, 7]
W_5 = [2, 5, 7]
W_6 = [3, 6, 7]

# set the number of Nodes
inst_N = 6
inst_M = 7

# Convert the list of lists into a NumPy array
inst_V = np.zeros((inst_N, inst_M))
for i, subset in enumerate([W_1, W_2, W_3, W_4, W_5, W_6]):
    for j in subset:
        inst_V[i, j-1] = 1  # -1 since element indices start from 1 in the input data

instance_data = {'V': inst_V, 'M': inst_M, 'N': inst_N}

JijSolverで解く#

jijsolverを用いて、この問題を解きましょう。

import jijsolver

interpreter = jm.Interpreter(instance_data)
instance = interpreter.eval_problem(problem)
solution = jijsolver.solve(instance, time_limit_sec=1.0)

解のチェック#

最後に、得られた解をチェックしてみましょう。

df = solution.decision_variables
x_indices = np.ravel(df[df["value"]==1]["subscripts"].to_list())
# show the result
for i in x_indices:
    print(f"W_{i+1} = {inst_V[i, :].nonzero()[0]+1}")

W_1 = [1 2 3]
W_2 = [4 5]
W_3 = [6 7]

これまでの計算から、予想された通りの結果を得ることができました。

厳密被覆問題

Contents

厳密被覆問題#