Set Packing

Set Packing#

Here we show how to solve the set packing problem using JijSolver and JijModeling. This problem is also mentioned in 4.2. Set Packing on Lucas, 2014, “Ising formulations of many NP problems”.

What is Set Packing?#

Let us consider the same setup as the Exact Cover problem, but now ask a different question: what is the largest number of subsets \(W_i\) that are all disjoint?

Mathematical Model#

Let \(x_i\) be a binary variable that takes on the value 1 if subset \(W_i\) is selected, and 0 otherwise.

Constraint: each element in \(U\) appears in exactly one selected subset#

This can be expressed as follows using \(V_{i, j}\) where it represents a mapping from a subset \(i\) to a set of elements \(j\) that it contains. Here we set \(V_{i, j}\) to be a matrix that is 1 when \(W_i\) contains \(j\) and 0 otherwise. $\( \sum_{i=1}^N x_i \cdot V_{i, j} = 1 \quad \text{ for } j = 1, \ldots, M \tag{1} \)$

Objective function: maximize the number of sets#

We simplify counting the number of sets we include as follows.

\[ \max \quad \sum_i x_i \tag{2} \]

Modeling by JijModeling#

Next, we show an implementation using JijModeling. We first define variables for the mathematical model described above.

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)

We use the same variables in the exact cover problem.

Constraint#

We implement the constraint, Equation (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)

We specify that our problem is aimed at maximizing an objective function by jm.Problem(..., sense=jm.ProblemSense.MAXIMIZE).

Objective function#

Next, we implement the objective function, Equation (2).

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

Let’s display the implemented mathematical model in 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}\]

Prepare an instance#

We prepare as below.

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}

Solve by JijSolver#

We solve this problem using jijsolver.

import jijsolver

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

Check the solution#

In the end, we display the solution obtained.

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]

As we expected, JijSolver successfully returns the optimal solution.

Contents