Skip to main content

Set Cover

Here we show how to solve the set cover problem using JijZept and JijModeling. This problem is also mentioned in 5.1. Set Cover on Lucas, 2014, "Ising formulations of many NP problems".

What is Set Cover?

We consider a set U={1,...,M}U = \{1,...,M\}, and subsets ViU(i=1,...,N)V_i \subseteq U (i = 1,...,N) such that

U=iViU = \bigcup_{i} V_i

The set covering problem is to find the smallest possible number of ViV_i s, such that the union of them is equal to UU. This is a generalization of the exact covering problem, where we do not care if some αU\alpha \in U shows up in multiple sets ViV_i

Mathematical model

Let xix_i be a binary variable that takes on the value 1 if subset ViV_i is selected, and 0 otherwise.

Constraint: each element in UU appears in at least one selected subset

This can be expressed as following using VV where it represents a mapping from a subset ii to a set of elements jj that it contains.

i=1NxiVi,j1 for j=1,,M(1)\sum_{i=1}^N x_i \cdot V_{i, j} \geq 1 \text{ for } j = 1, \ldots, M \tag{1}

Modeling by JijModeling

Next, we show how to implement above equation using JijModeling. We first define variables for the mathematical model described above.

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)

We use the same variables in the exact cover problem.

# 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)

We can check the implementation of the mathematical model on the Jupyter Notebook.


Problem:Set Covermin0s.t.onehoti=0N1xiVi,j1j{0,,M1}wherex1-dim binary variable\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}

Prepare an instance

We prepare as below.

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}

Solve by JijZept's SA

We solve this problem using JijZept JijSASampler. We also use the parameter search function by setting search=True.

import jijzept as jz

# set sampler
config_path = "../../../config.toml"
sampler = jz.JijSASampler(config=config_path)
# solve problem
response = sampler.sample_model(problem, instance_data, multipliers={"onehot": 0.5}, num_reads=100, search=True)

Check the solution

In the end, we extract the solution from the feasible solutions.

# get sampleset
sampleset = response.get_sampleset()
# extrace feasible samples
feasible_samples = sampleset.feasibles()
# get a solution
solution = feasible_samples[0].var_values["x"].values
# get the indices of x == 1
x_indices = [key[0] for key in solution.keys()]
for i in x_indices:
print(f"V_{i+1} = {inst_V[i, :].nonzero()[0]+1}")
V_6 = [3 6 7]
V_2 = [4 5]
V_1 = [1 2 3]

With the above calculation, we obtain a the result.