Exact Cover

Here we show how to solve the exact cover problem using JijZeptSolver and JijModeling. This problem is also described in 4.1. Exact Cover on Lucas, 2014, “Ising formulations of many NP problems”.

What is the Exact Cover Problem?

Consider a set \(U = \{1, \dots, M\}\) and a family of subsets \(W_i \subseteq U \ (i = 1, \dots, N)\) that covers \(U\). That is, assume that $\( U = \bigcup_{i} W_i \)$

holds.

The exact cover problem asks whether there exists a subfamily \(R\) of \(\left\{ W_i \right\}_{(i = 1, \dots, N)}\) such that the distinct elements of \(R\) are mutually disjoint and together cover \(U\).

Example

Let’s take a look at the following situation.

Let \(U\) be the universe of elements \(\{1, 2, 3, 4, 5, 6, 7\}\), and let \(W_i\) be a collection of subsets of \(U\), defined as follows:

\[ \begin{align} &W_1 = \{1, 2, 3\}, \\ &W_2 = \{4, 5\},\\ &W_3 = \{6, 7\},\\ &W_4 = \{3, 5, 7\},\\ &W_5 = \{2, 5, 7\},\\ &W_6 = \{3, 6, 7\}. \end{align} \]

The exact cover problem for this example asks whether there exists a subfamily \(R\) of the sets \(W_i\) such that the subsets in \(R\) are disjoint and their union is exactly \(U\). In other words, we are looking for a way to choose some of the subsets from \(W_i\) such that each element in \(U\) appears in exactly one subset of \(R\), and no two subsets in \(R\) share any elements. In this case, one possible exact cover is: $\( R = \{W_1, W_2, W_3\}. \)$

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

Consider the following expression:

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

In this expression, \(V_{i, j}\) represents a matrix that maps subset \(i\) to element \(j\). Specifically, \(V_{i, j}\) is \(1\) if \(W_i\) contains \(j\) and \(0\) otherwise.

For the example above, the constraints can be written as follows. $\( \begin{align} &x_1 = 1 \because 1 \text{ appears only in } W_1, \\ &x_1 + x_5 = 1 \because 2 \text{ appears in } W_1 \text{ and } W_5, \\ &x_1 + x_4 + x_6 = 1 \because 3 \text{ appears in } W_1, W_4, \text{ and } W_6, \\ &x_2 = 1 \because 4 \text{ appears only in } W_2, \\ &x_2 + x_4 + x_5 = 1 \because 5 \text{ appears in } W_2, W_4, \text{ and } W_5, \\ &x_3 + x_6 = 1 \because 6 \text{ appears in } W_3 \text{ and } W_6, \\ &x_3 + x_4 + x_5 + x_6 = 1 \because 7 \text{ appears in } W_3, W_4, W_5, \text{ and } W_6 . \end{align} \)$

Objective function: minimize the number of selected subsets

This can be expressed as follows. $\( \min \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

problem = jm.Problem('Exact Cover')

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

N is the number of subsets. M is the number of elements. V defines if subset \(i\) contains an element \(j\). We define a two-dimensional list of binary variables x.

Constraint

We implement the constraint, Equation (1).

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

Objective function

We implement an objective function.

problem += jm.sum(N, lambda i: x[i])

Let us display the implemented mathematical model in Jupyter Notebook.

problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Exact Cover}\\\displaystyle \min &\displaystyle \sum _{i=0}^{N-1}{{x}_{i}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{onehot}&\quad \displaystyle \sum _{i=0}^{N-1}{{x}_{i}\cdot {V}_{i,j}}=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} \]

Prepare an instance

Here, we use the same values from an example as we describe before.

import numpy as np

# set a list of W
W_1 = [1, 2, 3]
W_2 = [4, 5]
W_3 = [6, 7]
W_4 = [3, 5, 7]
W_5 = [2, 5, 7]
W_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([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 JijZeptSolver

We solve this problem using jijzept_solver.

import jijzept_solver

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

Check the solution

In the end, we display the solution obtained.

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 7]

With the above calculation, we obtain the expected result.