# 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 BinarySymbolGenerator
N = len(T) # The number of subsets
gen = BinarySymbolGenerator()
q = gen.array(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.constraint import one_hot
constraint = [one_hot(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 a logical model.

```
from amplify import BinaryQuadraticModel
model = sum(constraint)
```

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

```
from amplify.client import FixstarsClient
from amplify import Solver
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you use Amplify in a local environment or Google Colaboratory, enter your Amplify API token.
client.parameters.timeout = 1000
# Define and executec the solver
solver = Solver(client)
result = solver.solve(model)
```

Now, we check to see if we found a subset selection satisfying the constraints. Since
`Solver`

automatically filters the solutions that satisfy the constraints, if the `result`

is not
empty,
we 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.decode(result[0].values)
for i in np.where(values == 1)[0]:
print(f"T{i} : {T[i]}")
```