集合被覆問題

集合被覆問題#

ここではJijSolverとJijModelingを用いて、集合被覆問題を解く方法を説明します。 Lucas, 2014, “Ising formulations of many NP problems” 5.1. Set Cover でも触れられています。

集合被覆問題とは#

集合\(U = \{1, 2, \dots, M\}\)とその部分集合\(V_i \subseteq U \ (i=1, \dots, N)\)としましょう。 つまり

\[ U = \bigcup_i V_i \]

が成り立ちます。 集合被覆問題は、\(U\)と同じ集合を\(V_i\)の和集合から作るのに、最小の\(V_i\)数を見つける問題です。 これは厳密被覆問題を一般化したもので、要素\(\alpha \in U\)が複数の部分集合\(V_i\)に現れるかどうかは問題ではありません。

数理モデル#

部分集合\(V_i\)を選択するとき1、そうでないとき0となるようなバイナリ変数\(x_i\)を導入しましょう。

制約: \(U\)の各要素は、少なくとも1回は選ばれた部分集合内に現れなければならない

部分集合\(i\)からそれらが含む要素の集合\(j\)へのマッピングを表現したものを、\(V_{i, j}\)のように書きましょう。 すると、この制約を次のように書けます。

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

JijModelingによるモデル化#

次にJijModelingを用いて、方程式を実装しましょう。 最初に、上述の数理モデルで用いられた変数を定義します。

import jijmodeling as jm

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

厳密被覆問題と同じ変数を用います。 次に制約の実装を行います。

# set problem
problem = jm.Problem('Set 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)

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

problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{Set Cover} & & \\& & \min \quad \displaystyle 0 & \\\text{{s.t.}} & & & \\ & \text{onehot} & \displaystyle \sum_{i = 0}^{N - 1} x_{i} \cdot V_{i, j} \geq 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 V
V_1 = [1, 2, 3]
V_2 = [4, 5]
V_3 = [5, 6, 7]
V_4 = [3, 5, 7]
V_5 = [2, 5, 7]
V_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([V_1, V_2, V_3, V_4, V_5, V_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())
for i in x_indices:
    print(f"V_{i+1} = {inst_V[i, :].nonzero()[0]+1}")

V_1 = [1 2 3]
V_2 = [4 5]
V_6 = [3 6 7]

これまでの実装から、集合被覆問題の解を得ることができました。

Contents