#
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.

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.

```
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.

```
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$).

```
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$.

```
from amplify import equal_to
constraint = equal_to(q, N)
```

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

```
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.

```
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.

```
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)
```