# Example NP
problems published in A. Lucas, *Front. Phys.* (2014) - Exact cover problem¶

This example code implements the **exact cover problem** introduced in the paper A. Lucas, "Ising
formulations
of many NP problems", *Front. Phys.* (2014) using Fixstars Amplify. Other NP-complete and
NP-hard problems introduced in the same paper are also discussed below (the corresponding sections in
the
paper are shown in the brackets).

- Graph partitioning problem (Sec. 2.2).
- Maximum clique problem (Sec. 2.3)
**Exact cover problem**(Sec. 4.1)- Set packing problem (Sec. 4.2)
- Minimum vertex cover problem (Sec. 4.3)
- Satisfiability problem (SAT) (Sec. 4.4)
- Minimal maximal matching problem (Sec. 4.5)
- Graph coloring problem (Sec. 6.1)
- Clique cover problem (Sec. 6.2)
- Job sequencing problem with integer lengths (Sec. 6.3)
- Hamiltonian cycle problem (Sec. 7.1)
- Directed feedback vertex set problem (Sec. 8.3)
- Minimum feedback edge set problem (Sec. 8.5)
- Graph isomorphism problem (Sec. 9)

## Exact cover problem¶

Suppose we have a set $S$ and are given subsets $T_0, T_1, \ldots, T_{N-1}$ of $S$.

The problem of choosing some of $T_0, T_1, \dots, T_{N-1}$ and determining whether the chosen
multiple
subsets can be partitions of $S$ is called the **exact covering problem**. That is,
determine
whether any element of $S$ can be contained in exactly one of the chosen subsets.

For example, if $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$, as shown in the figure below, then $T_0 = \{1, 2, 3, 6, 9\}$, $T_1 = \{1, 2, 5, 8\}$, $T_2 = \{4, 7\}$, $T_3 = \{4, 5\}$, $T_4 = \{6, 9\}$, $T _5 = \{3\}$. If we choose $T_1$, $T_2$, $T_4$, and $T_5$, these are the partitions of $S$.

This example program uses Fixstars Amplify to solve the exact cover problem. The formulation follows that of Sec. 4.1 of A. Lucas, Front. Phys. (2014).

## Problem definition¶

As an example, we define the problem mentioned above as follows.

```
S = [1, 2, 3, 4, 5, 6, 7, 8, 9] # set S
T = [[1, 2, 3, 6, 9], [1, 2, 5, 8], [4, 7], [4, 5], [6, 9], [3]] # subsets of S
```

## Formulation¶

### Decision variables¶

Let $N$ binary variables $q$ be mapped to $T_0, T_1, \ldots, T_{N-1}$ to indicate whether to choose the corresponding subset $T_i$. If $T_i$ is chosen, $q_i$ is $1$; if not, $0$.

For example, when choosing four subsets $T_1$, $T_2$, $T_4$, and $T_5$, $q$ is as follows.

Subset | $$T_0$$ | $$T_1$$ | $$T_2$$ | $$T_3$$ | $$T_4$$ | $$T_5$$ |
---|---|---|---|---|---|---|

$$q$$ | 0 | 1 | 1 | 0 | 1 | 1 |

### Objective function¶

Since this problem is to find one solution that satisfies the condition, the objective function is $0$ (not considered).

Note that if you want to make the number of subsets you choose as small as possible, which is an advanced version of the present problem, you need to set $\displaystyle \sum_{i = 0}^{N-1} q_i$ as the objective function since this is an optimization problem.

### Constraints¶

The condition "every $S$ element is contained in exactly $1 of the chosen subset" can be reworded as "for any element $x$ of $S$, exactly $1$ of the subset $T_i$ containing $x$ is chosen":

$$ \sum_{T_i \ni x} q_i = 1 \quad \text{for} \quad x \in S. $$

## Implementation¶

Using the problem and formulation created above, let us implement and solve the problem. First,
create as
many binary variables $q$ as there are subsets using the `BinarySymbolGenerator`

in the
Fixstars Amplify SDK.

```
from amplify import VariableGenerator
N = len(T) # The number of subsets
gen = VariableGenerator()
q = gen.array("Binary", N)
```

Next, we construct the constraints. As mentioned earlier, for each element $x$ of $S$, we need to satisfy the constraints that precisely one of the subsets containing $x$ is chosen.

```
from amplify import one_hot, sum as amplify_sum
constraints = amplify_sum(
one_hot(amplify_sum(q[i] for i in range(N) if x in T[i])) for x in S
)
```

Now, let us convert the created constraints into an optimization model.

```
from amplify import Model
model = Model(constraints)
```

Let us set the client and execute the solver with Fixstars Amplify Annealing Engine (AE).

```
from amplify import FixstarsClient, solve
from datetime import timedelta
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you use Amplify in a local environment or Google Colaboratory, enter your Amplify API token.
client.parameters.timeout = timedelta(milliseconds=1000) # timeout is 1000 ms
# Solve the problem
result = solve(model, client)
```

Now, we check to see if we found a subset selection satisfying the constraints. Since Amplify SDK
automatically filters the solutions that satisfy the constraints, if the `result`

is not
empty,
you know that there is a solution that satisfies the constraints.

```
if len(result) == 0:
print("No solution has been found.")
else:
print("A solution has been found.")
```

Finally, let us visualize the results. Also, you can try changing the set $S$ or its subset $T_i$ to see if the exact covering is possible.

```
import numpy as np
values = q.evaluate(result.best.values)
for i in np.where(values == 1)[0]:
print(f"T{i} : {T[i]}")
```