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

This example code implements the Graph partitioning 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)

Graph partitioning problem¶

Given a graph $G$ with $2N$ vertices, the graph partitioning problem is to find a way to partition $G$ into two sets of $N$ vertices each, such that the number of edges of $G$ connecting $2$ points belonging to different sets is minimized.

For example, in the following graph, if we partition the 8 vertices into a set of 4 orange vertices and a set of 4 blue vertices, there are 2 edges connecting the blue and orange vertices. It is also easy to see that this partition is the optimal solution.

Graph

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

Problem definition¶

First, as an example, create a graph $G$ with $2N$ vertices using NetworkX.

In [ ]:

import networkx as nx

N = 4  # Half the number of vertices in the graph
G = nx.Graph()
G.add_nodes_from(range(2 * N))
# Define edges connecting two vertices
edge_list = [
    (0, 1),
    (0, 2),
    (1, 2),
    (2, 3),
    (3, 4),
    (3, 5),
    (3, 6),
    (4, 5),
    (5, 6),
    (6, 7),
]
G.add_edges_from(edge_list)

pos = nx.circular_layout(G)

nx.draw_networkx(G, node_size=300, font_color="w", pos=pos)

Formulation¶

Decision variables¶

Let each of $2N$ binary variables $q$ correspond to each vertex in $G$ to indicate which set each vertex belongs to. For example, if $q=0$ is the vertex set denoted by blue and $q=1$ is the vertex set denoted by orange, the binary variable combinations corresponding to the partitioning in the figure below are shown in the table below.

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

Objective function¶

To solve the graph partitioning problem, we can determine the value of the decision variable $q$ so as to minimize the number of edges connecting vertices belonging to different sets.

For vertices $u$ and $v$ of $G$ to belong to different sets, the exclusive OR (xor) of $q_u$ and $q_v$ must be 1, which is expressed as $-2q_u q_v + q_u + q_v$ in quadratic form. Among all pairs $(u, v)$ of vertices connected by edges, the objective function is the minimum number of $(u, v)$ where $u$ and $v$ belong to different sets. Therefore, the objective function is:

$$ \sum_{(u, v) \in E} \operatorname{xor}(q_u, q_v) = \sum_{(u, v) \in E} -2q_uq_v + q_u + q_v. $$

Constraints¶

For the partition of the vertex set of $G$ represented by the decision variable $q$ to be two sets consisting of $N$ vertices, it is necessary and sufficient that there are $N$ binary variables, which are $0$ and $1$, respectively. Therefore, the sum of $q_i$ is $N$:

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

Implementation¶

With the problem and formulation described above, let's implement and solve the problem. First, create binary decision variables $q$ using the BinarySymbolGenerator in the Fixstars Amplify SDK.

In [ ]:

from amplify import VariableGenerator

gen = VariableGenerator()
q = gen.array("Binary", 2 * N)

Next, we create the objective function $\sum_{(u, v) \in E} \operatorname{xor}(q_u, q_v)$. The logical operator, q[u] ^ q[v], is overloaded for the binary decision variables in Fixstars Amplify SDK, and $\operatorname{ xor}(q_u, q_v)$ is computed to take the same value as a second-order polynomial ($-2q_uq_v + q_u + q_v$).

In [ ]:

from amplify import sum

cost = sum([q[u] ^ q[v] for u, v in G.edges])

Next, we create a constraint condition. As mentioned above, the constraint condition is that the sum of the $2N$ binary decision variables is exactly $N$.

In [ ]:

from amplify import equal_to

constraint = equal_to(q, N)

Let us combine the created objective function and constraints into an optimization model.

In [ ]:

model = cost + constraint

Now, we define the client and solve the logical model on 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.parameters.timeout = timedelta(milliseconds=1000)  # timeout is 1000 ms
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"  # If you use Amplify in a local environment, enter the Amplify API token.

# 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, visualize the resulting graph partition. Since the problem setup is similar to the graph in the introduction, the resulting partition will be similar. You can try changing the shape of the graph and the number of edges to see if you can achieve the correct partition.

In [ ]:

values = q.evaluate(result.best.values)
colors = [f"C{int(value)}" for value in values]

nx.draw_networkx(G, node_size=600, node_color=colors, font_color="w", pos=pos)