Travelling Salesman Problem¶
This section describes how to solve the traveling salesman problem using Amplify.
Formulation of the Traveling Salesman Problem¶
The Traveling Salesman Problem is a combinatorial optimization problem to find the shortest route that visits all cities exactly once, given a set of cities and the distances between each pair of cities.
In order to use the Ising machine, the combinations of paths need to be represented by polynomials with respect to binary or Ising variables. Every combination of paths can be represented by a table of variables that shows which city is visited in which order. For example, the following table for four cities will represent the route $A \rightarrow C \rightarrow B \rightarrow D \rightarrow A$.
turn  A  B  C  D 

1st  1  0  0  0 
2nd  0  0  1  0 
3rd  0  1  0  0 
4th  0  0  0  1 
5th  0  0  0  1 
We assign binary variables $\left\{0, 1\right\}$ to each element of the table. We interpret a path by following the cities where $1$ is assigned in the right order from 1st to 4th. That is, for a traveling salesman problem in $N$ cities, it suffices to have $N^2$ variables.
Let $q_{n,i}$ be each variable in the above table, using the route order $n$ and the city index $i$. Then the total distance of travel routes are represented as follows;
$$ \sum_{n=0}^{N1}{\sum_{i=0}^{N1}{\sum_{j=0}^{N1}{ d_{ij} q_{n, i} q_{n+1, j} }}} $$
where $d_{ij}$ is the distance traveled between cities labeled by $i$ and $j$. Since $d_{ij} q_{n, i} q_{n+1, j}$ adds $d_{ij}$ when the both variables equal $1$, the above expression is equal to the sum of total distance traveled. Note that the indices start at $0$ for convenience in later programmatic coding.
However, this is not a sufficient formulation. This is because the above variable table does not take into account the constraints of "visiting all cities" and "visiting only one city at a time". As an extreme example, the combination of not moving from the first city is allowed. We thus need to impose the following constraints on all the rows and columns of the variables table.
$$ \begin{align*} \sum_{i=0}^{N1}{q_{n, i}} = 1 &, \; & n \in \left\{0, 1, \cdots, N  1 \right\} \\ \sum_{n=0}^{N1}{q_{n, i}} = 1 &, \; & i \in \left\{0, 1, \cdots, N  1 \right\} \end{align*} $$
These imply the constraints that $1$ can appear only once in each row and each column of the variable table.
Summarizing the above, it turns out that we need to find the minimum value of the following polynomial:

Objective function $$ \sum_{n=0}^{N1}{\sum_{i=0}^{N1}{\sum_{j=0}^{N1}{ d_{ij} q_{n, i} q_{n+1, j} }}} $$

Constraints $$ \begin{align*} \sum_{i=0}^{N1}{q_{n, i}} = 1 &, \; & n \in \left\{0, 1, \cdots, N  1 \right\} \\ \sum_{n=0}^{N1}{q_{n, i}} = 1 &, \; & i \in \left\{0, 1, \cdots, N  1 \right\} \end{align*} $$
Creating a problem¶
First, we create locations of the cities and the distances between each city, which will be the input
for
the Traveling Salesman Problem. Here we use numpy
to place the cities at random locations
on
a twodimensional plane and generating the distance matrix.
In this tutorial, the number of cities created will be 32.
import numpy as np
def gen_random_tsp(num_cities: int):
rng = np.random.default_rng()
# locations
locations = rng.random(size=(num_cities, 2))
# distance matrix
x = locations[:, 0]
y = locations[:, 1]
distances = np.sqrt(
(x[:, np.newaxis]  x[np.newaxis, :]) ** 2
+ (y[:, np.newaxis]  y[np.newaxis, :]) ** 2
)
return locations, distances
NUM_CITIES = 32
locations, distances = gen_random_tsp(NUM_CITIES)
The following will plot the coordinates of each city.
import matplotlib.pyplot as plt
def show_plot(locations: np.ndarray):
plt.figure(figsize=(7, 7))
plt.xlabel("x")
plt.ylabel("y")
plt.scatter(locations[:, 0], locations[:, 1])
plt.show()
show_plot(locations)
Formulation¶
First, we create a table of variables that represent the order of visits and destinations in the circuit. A variable table of shape $(N + 1) \times N$ will be needed, but the last row should be set to take the same values as the first row.
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(NUM_CITIES + 1, NUM_CITIES))
q[NUM_CITIES, :] = q[0, :]
print(q)
We use this q
to create the objective function.
from amplify import einsum, Poly
objective: Poly = einsum("ij,ni,nj>", distances, q[:1], q[1:]) # type: ignore
The function einsum
is used for the summation operation in the objective function.
q[:1]
is the $N\times N$ array excluding the last row of q
, and
q[1:]
is the $N\times N$ array excluding the first row of q
. Writing the
former
as $q^U$ and the latter as $q^D$, the objective function $\displaystyle \sum_{n = 0}^{N  1}\sum_{i =
0}^{N  1}\sum_{j = 0}^{N  1} d_{ij}q_{n,i} q_{n+1,j}$ can be expressed as $\displaystyle\sum_{n, i,
j}
d_{ij}q^U_{n,i} q^D_{n,j}$. Therefore, the objective function is expressed by giving the subscripts of
the
three arrays to the right of the sigma sign as the first argument of the einsum
function
and
the three arrays as the second and subsequent arguments.
Note¶
Using the amplify.sum()
function for summing polynomial objects, it can be written as
below:
from amplify import sum as amplify_sum
cost = amplify_sum(
range(NUM_CITIES),
lambda n: amplify_sum(
range(NUM_CITIES),
lambda i: amplify_sum(
range(NUM_CITIES), lambda j: distances[i, j] * q[n, i] * q[(n + 1) % ncity, j]
),
),
)
Next, we construct the constraints. The onehot constraints are created with the
one_hot()
function.
from amplify import one_hot
# onehot constraint for each row
row_constraints = one_hot(q[:1], axis=1)
# onehot constraint for each column
col_constraints = one_hot(q[:1], axis=0)
constraints = row_constraints + col_constraints
Finally, the objective function and all the constraints are added together to create a model object. Here, we need to pay attention to the strength of the constraints. This is because the appropriate strength of the constraints depends on the objective function and needs to be sufficiently large. However, making the strength of the constraints as small as possible tends to improve the results output by the Ising machine.
See reference [1] for a discussion on the strength of the constraints in the traveling salesman problem. Here, we set the maximum value of the distance matrix as a large enough value. Using this value, we create a logical model object as follows:
constraints *= np.amax(distances) # Set the strength of the constraint
model = objective + constraints
This completes the preparation for the formulation.
Running the Ising machine¶
We create a client for the Ising machine and set the parameters. We then create the solver with the configured client.
from amplify import FixstarsClient, solve
from datetime import timedelta
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000) # Timeout is 1 second
# Solve the problem
result = solve(model, client)
if len(result) == 0:
raise RuntimeError("Any one of constraints is not satisfied.")
If the result
object is empty, it means that no solution satisfying the constraints was
obtained. In this case, you need to change the parameters of the Ising machine or the constraint
weight.
Analysis of results¶
The object
represents the evaluation value of the objective function. In this
formulation,
it corresponds to the total distance traveled.
result.best.objective
The values
is a dictionary which provides the mapping between input variables and
solution
values. It is hard to evaluate it as it is, so we obtain it into the same format as the variables
array
q
as follows:
q_values = q.evaluate(result.best.values)
This shows that the constraint is indeed satisfied, since $1$ appears only once in each row and
column.
We can find the path by getting the column index where the $1$ appears, so we can use the
numpy
function to check it, as follows (converted to an array numpy.ndarray
to
use the numpy
function).
route = np.where(np.array(q_values) == 1)[1]
print(route)
Finally we display the route found above. It can be plotted with the following function:
def show_route(route: np.ndarray, distances: np.ndarray, locations: np.ndarray):
path_length = sum([distances[route[i]][route[i + 1]] for i in range(NUM_CITIES)])
x = [i[0] for i in locations]
y = [i[1] for i in locations]
plt.figure(figsize=(7, 7))
plt.title(f"path length: {path_length}")
plt.xlabel("x")
plt.ylabel("y")
for i in range(NUM_CITIES):
r = route[i]
n = route[i + 1]
plt.plot([x[r], x[n]], [y[r], y[n]], "b")
plt.plot(x, y, "ro")
plt.show()
return path_length
show_route(route, distances, locations)