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

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

Maximum clique problem¶

For a graph $G$, a subset of the vertices of $G$ such that an edge connects any two vertices in the subset is called a clique. The maximum clique problem is to find the clique with the most significant number of elements.

For example, all orange vertices in the graph below are connected by edges, so the four orange vertices form a clique. We can also see that there is no clique consisting of 5 vertices since there are only 3 vertices with degrees (the number of edges coming from a vertex) greater than or equal to 4.

Graph

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

Problem definition¶

As an example, create a graph $G$ using NetworkX. Since the graph created is the same as the above example graph, the maximum number of elements in the clique is 4, as mentioned above.

In [ ]:

import networkx as nx
    
N = 7  # The number of vertices in the graph
G = nx.Graph()
G.add_nodes_from(range(N))
# Define edges connecting two vertices
edge_list = [
    (0, 1),
    (0, 6),
    (1, 2),
    (1, 3),
    (1, 4),
    (1, 6),
    (2, 3),
    (3, 4),
    (3, 5),
    (3, 6),
    (4, 6),
    (5, 6),
]
G.add_edges_from(edge_list)
    
pos = nx.circular_layout(G)
    
nx.draw_networkx(G, node_size=600, font_color="w", pos=pos)

Formulation¶

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

Decision variables¶

Let each of $N$ binary variables $q$ correspond to each vertex to indicate whether it is included in the clique. If the clique includes vertex $i$, $q_i$ is $1$, and if not, $0$.

For example, a clique consisting of vertex 1, vertex 3, vertex 4, and vertex 6 as shown in the figure below, is represented as in the table below.

Index of vertex	0	1	2	3	4	5	6
$q$	0	1	0	1	1	0	1

Objective function¶

Since the size of the clique should be as large as possible, the objective function is:

$$ -\sum_{i = 0}^{N - 1} q_i $$

We added the minus sign to make the maximization problem a minimization problem.

Constraints¶

For the binary variable $q$ to correspond to a clique, we must impose the constraint that "an edge connects every vertex in the clique." Using this contraposition, we can rephrase the condition as "if vertices $u$ and $v$ are not connected by an edge, then at least one of $u$ and $v$ is not contained in the clique." We can write the condition as:

$$ q_uq_v = 0 \quad\text{for}\quad (u, v) \notin E $$

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

Implementation¶

Using the problem and formulation created above, let us implement and solve the problem. First, create binary decision variables $q$ using the BinarySymbolGenerator in Fixstars Amplify SDK.

In [ ]:

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

Next, create the objective function. As introduced earlier, the objective function equals $-1$ times the number of vertices in the clique and is represented by $-\sum_{i=0}^{N-1}q_i$.

In [ ]:

cost = -q.sum()

Next, we create the constraint condition. As mentioned earlier, the constraint is equivalent to the condition that edges connect all vertices in the clique, and we can express this by its contraposition $q_u q_v = 0 \ \left( (u, v) \notin E\right)$.

In [ ]:

from amplify import equal_to, sum as amplify_sum
    
constraints = amplify_sum(equal_to(q[u] * q[v], 0) for u, v in nx.non_edges(G))

Now, we can combine the objective function and constraints constructed above into an optimization model.

In [ ]:

model = cost + constraints

Let us define the client and solve the logical model with the Fixstars Amplify Annealing Engine (AE). 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 [ ]:

from amplify import FixstarsClient, solve
from datetime import timedelta
    
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"  # when you use Amplify in a local environment or Google Colaboratory, put your Amplify API token here.
client.parameters.timeout = timedelta(milliseconds=1000)  # timeout is 1000 ms
    
# Solve the problem
result = solve(model, client)
    
if len(result) == 0:
    print("No solution has been found.")
else:
    print("A solution has been found.")

Finally, we visualize the results. Since the problem setup is the same as the graph in the introduction, the maximum clique obtained is also the same. You can try changing the shape of the graph and the number of edges to see if you can correctly obtain the maximum clique.

In [ ]:

values = q.evaluate(result.best.values)
colors = ["C1" if value == 1 else "C0" for value in values]
nx.draw_networkx(G, node_size=600, node_color=colors, font_color="w", pos=pos)