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

This example code implements the clique 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)
Minimum maximum 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)

Clique cover problem¶

Given a graph $G$ and an integer $K$, clique cover problem is the problem to determine whether the vertices of $G$ can be painted with a $K$ color so that every pair of vertices of the same color is connected by an edge.

For example, the following graph shows that it is possible to cover $G$ with $2$ colors (cliques) because all three blue vertices are connected by edges, and all three orange vertices are also connected by edges.

Here, we create a program that uses Fixstars Amplify to search for a way to paint the vertices. The formulation follows the one in section 6.2 of A. Lucas, Front. Phys. (2014).

Problem definition¶

First, for example, let us create a graph $G$ using NetworkX. Also, let $K$, the number of colors, be $2$.

In [ ]:

import networkx as nx
    
N = 6  # Number of vertices of the graph
K = 2  # Number of colors
G = nx.Graph()
G.add_nodes_from(range(N))
edge_list = [
    (0, 1),
    (0, 2),
    (1, 2),
    (1, 3),
    (1, 4),
    (2, 3),
    (2, 5),
    (3, 4),
    (3, 5),
    (4, 5),
]
G.add_edges_from(edge_list)
    
pos = nx.spring_layout(G, seed=0)
    
nx.draw_networkx(G, node_size=600, font_color="w", pos=pos)

The resulting graph is the same as the one shown in the introduction. Therefore, the condition is satisfied by painting the vertices $0$, $1$, and $2$ in one color and the vertices $3$, $4$, and $5$ in the other color.

Formulation¶

Let $N$ be the number of vertices of $G$ below.

Decision variables¶

Create a binary decision variable table $q$ of $N \times K$, where each vertex is painted with a color specified by a corresponding decision variable. When vertex $i$ is painted with the $j$-th color, the binary variable in the $i$ row $j$ column of $q$ is $1$.

For example, when vertices $0$, $1$, and $2$ are painted with the $0$th color and vertices $3$, $4$, and $5$ are painted with the $1$st color, the variable table $q$ is as follows.

$q$	0th color	1st color
Vertex 0	1	0
Vertex 1	1	0
Vertex 2	1	0
Vertex 3	0	1
Vertex 4	0	1
Vertex 5	0	1

Objective function¶

Since the clique cover problem is to find one that satisfies the condition, No objective function is considered.

Constraints¶

For $G$ to be covered by $K$ cliques according to $q$ and the corresponding coloring scheme, we need the following constraints.

Condition 1 : Each vertex of $G$ is painted with exactly a single color.
Condition 2: Vertices of the same color are always connected by an edge.

Condition 1 is the constraint that there is precisely one $1$ in each row, and we can express this as:

$$ \sum_{j = 0}^{K-1} q_{i, j} = 1 \quad \text{for} \quad i \in \{0, 1, \ldots, N-1\}. $$

Also, considering the contraposition of condition 2, condition 2 is rephrased as "$2$ vertices not connected by an edge are not painted in the same color".

The condition can be written as:

$$ q_{u, j} q_{v, j} = 0 \quad \text{for} \quad (u, v) \notin E, \ j \in \{0, 1, \ldots, K - 1\} $$

Here, $E$ is an edge set of $G$.

Implementation¶

Using the problem and formulation described above, let us implement and solve the problem. First, we create $N\times K$ binary variables $q$ using BinarySymbolGenerator in Fixstars Amplify SDK.

In [ ]:

from amplify import VariableGenerator
    
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, K))

Next, we construct the constraint corresponding to condition 1. Condition 1 is condition that there is only one 1 in each row of $q$, so we can use one_hot to express this condition.

In [ ]:

from amplify import one_hot
    
constraint1 = one_hot(q, axis=1)

Then, let us construct a constraint condition corresponding to the condition 2. The condition 2 is, $q_{u, j} q_{v, j} = 0 \bigl((u, v) \notin E, \ j \in \{0, 1, \ldots, K - 1\}\bigr)$.

In [ ]:

from amplify import equal_to, sum as amplify_sum
    
constraint2 = amplify_sum(
    equal_to(q[u, j] * q[v, j], 0)
    for u in range(N)
    for v in range(N)
    for j in range(K)
    if u < v and (u, v) not in G.edges and (v, u) not in G.edges
)

Now, we combine the abovementioned constraints and convert them into an optimization model.

In [ ]:

from amplify import Model
    
model = Model(constraint1 + constraint2)

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

In [ ]:

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)

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.

In [ ]:

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

Lastly, let us visualize the solution.

In [ ]:

import numpy as np
    
values = q.evaluate(result.best.values)
    
colors = [f"C{i}" for i in np.where(values == 1)[1]]
nx.draw_networkx(G, node_size=600, node_color=colors, font_color="w", pos=pos)