Example NP problems published in A. Lucas, Front. Phys. (2014) - Hamiltonian cycle problem¶
This example code implements the Hamiltonian cycle 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)
Hamiltonian cycle problem¶
Given a graph , we call a closed path a Hamiltonian cycle if it passes through all vertices of once and returns to the origin. In general, when the size of the graph is large, it is difficult to determine in realistic time whether a Hamiltonian cycle exists in the graph.
Here, we use Fixstars Amplify to solve this Hamiltonian cycle problem. This problem corresponds to section 7.1 of A. Lucas, Front. Phys. (2014).
Problem definition¶
First, we create a graph to be considered in this sample program using NetworkX. The number of vertices is .
import networkx as nx
N = 5 # Number of vertices of the graph
G = nx.Graph()
G.add_nodes_from(range(N))
edge_list = [(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 4), (3, 4)]
pos = nx.circular_layout(G) # Save the layout of the graph
G.add_edges_from(edge_list)
nx.draw_networkx(G, node_size=600, font_color="w", pos=pos)
Formulation¶
Decision variables¶
Let us consider binary decision variables , representing which vertex to pass and when. That is, a component of the binary decision variables corresponds to passing the vertex at -th visit () or not (). For example, when the binary variables are as follows, it corresponds to a closed path in the above graph.
Order \ Index of vertex | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
1st | 1 | 0 | 0 | 0 | 0 |
2nd | 0 | 1 | 0 | 0 | 0 |
3rd | 0 | 0 | 0 | 1 | 0 |
4th | 0 | 0 | 0 | 0 | 1 |
5th | 0 | 0 | 1 | 0 | 0 |
Objective function¶
Since the Hamiltonian cycle problem is to find one that satisfies the conditions, no objective function is considered.
Constraints¶
For to represent a Hamiltonian cycle, we need the following:
-
The -th vertex must be a single vertex. We can rephrase this condition as there being exactly a single in each row of the binary variable table .
-
Each vertex must be passed through exactly times. We can rewrite this condition as there being exactly a single in each column of the binary variable table .
-
No transfers are allowed between vertices that are not connected. That is, when no edge connects between vertices and , both and must not be .
The above conditions 1-3 can be written in mathematical expressions as follows, respectively.
Here, denotes the edge set of .
Also, when the binary variables satisfy all conditions 1-3, corresponds to a Hamiltonian cycle of .
Implementation¶
Using the problem and formulation described above, let us implement and solve the problem. First, use
BinarySymbolGenerator
in Fixstars Amplify SDK to create binary decision
variables
.
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, N))
Next, we create the constraints corresponding to the conditions 1 and 2. Since these are conditions
that
there is only one in each row and column of , we can write them using one_hot
.
from amplify import one_hot
row_constraints = one_hot(q, axis=1)
col_constraints = one_hot(q, axis=0)
We can print the abovementioned constraints and check that the one_hot
condition is
correctly imposed on each row and column.
row_constraints
col_constraints
Next, we create the constraint corresponding to the condition 3. Condition 3 is the condition that ( and are two vertices not connected by an edge). Note that implies when .
from amplify import equal_to, sum as amplify_sum
edge_constraints = amplify_sum(
equal_to(q[k, i] * q[(k + 1) % N, j], 0) + equal_to(q[k, j] * q[(k + 1) % N, i], 0)
for (i, j) in nx.non_edges(G)
for k in range(N)
)
The necessary constraints are in place. Finally, we combine to create the optimization model.
from amplify import Model
model = Model(row_constraints + col_constraints + edge_constraints)
Let us set the client and execute the solver with Fixstars Amplify Annealing Engine (AE).
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)
Now, we check whether there is a Hamiltonian cycle in the graph. Since Amplify SDK automatically
filters
the solutions that satisfy the constraints, if the result
is not empty, you know that a
solution has been found that satisfies the constraints.
if len(result) == 0:
print("No Hamiltonian cycle has been found.")
else:
print("A Hamiltonian cycle has been found.")
Finally, let us visualize the solution. Below is the found Hamiltonian cycle in orange color.
import numpy as np
# Setting default attributes for edges
for edge in G.edges.values():
edge["color"] = "k"
edge["width"] = 1.0
# Setting attributes for edges constituting the found Hamiltonian cycle
values = q.evaluate(result.best.values)
route = np.where(values == 1)[1]
for i, j in zip(route, np.roll(route, -1)):
G.edges[i, j]["color"] = "C1"
G.edges[i, j]["width"] = 2.0
# Visualize
edge_color = [edge["color"] for edge in G.edges.values()]
edge_width = [edge["width"] for edge in G.edges.values()]
nx.draw_networkx(
G, node_size=600, font_color="w", pos=pos, edge_color=edge_color, width=edge_width
)