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.

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.

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.

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

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

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.

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.