集合パッキング問題

集合パッキング問題#

ここでは、JijSolverとJijModelingを用いて、集合パッキング問題を解く方法を説明します。この問題は、Lucas, 2014, “Ising formulations of many NP problems” 4.2. Set Packingでも触れられています。

集合パッキング問題とは#

厳密被覆問題と同じ状況を考えますが、こちらは「すべてが互いに素な部分集合\(W_i\)の最大数はいくつか？」を問う問題です。

数理モデル#

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

制約: \(U\)の各要素は、選ばれた部分集合内に1つしか現れてはならない#

この制約を表現するために、\(i\)番目の部分集合が要素\(j\)を含むことを表すマッピング変数\(V_{i, j}\)を用いましょう。すなわち\(V_{i, j}\)は、\(W_i\)が要素\(j\)を含むとき1、そうでないとき0となるような行列です。

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

目的関数: 選択された集合数を最大にする#

選択された集合数をカウントし、それを最大化することは、次のようにまとめることができます。

\[ \max \quad \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)

これらは、厳密被覆問題で用いた変数と同じものです。

制約#

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

# set problem
problem = jm.Problem('Set Packing',sense = jm.ProblemSense.MAXIMIZE)
# 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)

jm.Problem(..., sense=jm.ProblemSense.MAXIMIZE)とすることで、目的関数の最大化を目指す問題であることを指定できます。

目的関数#

次に、式(2)の目的関数を実装しましょう。

# set objective function: maximize the number of sets
problem += x[:].sum()

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

problem

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{Set Packing} & & \\& & \max \quad \displaystyle \sum_{\ast_{0} = 0}^{N - 1} x_{\ast_{0}} & \\\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]
W_4 = [7]
W_5 = [2, 5, 7]
W_6 = [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]
W_4 = [7]

予想通り、JijSolverが最適解を求めることに成功しました。

集合パッキング問題

Contents

集合パッキング問題#