集合パッキング問題

集合パッキング問題#

ここでは、JijZeptSolverと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

problem = jm.Problem('Set Packing', sense=jm.ProblemSense.MAXIMIZE)

N = problem.Natural('N')
M = problem.Natural('M')
V = problem.Natural('V', shape=(N, M))
x = problem.BinaryVar('x', shape=(N,))

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

制約#

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

problem += problem.Constraint('onehot', lambda j: jm.sum(N, lambda i: x[i]*V[i, j]) <= 1, domain=M)

目的関数#

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

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

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

problem
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Set Packing}\\\displaystyle \max &\displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{onehot}&\quad \displaystyle \sum _{i=0}^{N-1}{{x}_{i}\cdot {V}_{i,j}}\leq 1\quad \forall j\;\text{s.t.}\;j\in \left\{0,\ldots ,M-1\right\}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}M&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\V&\in \mathop{\mathrm{Array}}\left[N\times M;\mathbb{N}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{N}\\\end{alignedat}\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}

JijZeptSolverで解く#

jijzept_solverを用いて、この問題を解いてみましょう。

import jijzept_solver

instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)

解の確認#

最後に、得られた解を表示してみましょう。

df = solution.decision_variables_df
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]

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

目次