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

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}^{N-1}{\sum_{i=0}^{N-1}{\sum_{j=0}^{N-1}{ 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}^{N-1}{q_{n, i}} = 1 &, \; & n \in \left\{0, 1, \cdots, N - 1 \right\} \\ \sum_{n=0}^{N-1}{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}^{N-1}{\sum_{i=0}^{N-1}{\sum_{j=0}^{N-1}{ d_{ij} q_{n, i} q_{n+1, j} }}}$$

• Constraints $$\begin{align*} \sum_{i=0}^{N-1}{q_{n, i}} = 1 &, \; & n \in \left\{0, 1, \cdots, N - 1 \right\} \\ \sum_{n=0}^{N-1}{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 two-dimensional plane and generating the distance matrix.

In this tutorial, the number of cities created will be 32.

The following will plot the coordinates of each city.

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.

We use this q to create the objective function.

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 one-hot constraints are created with the one_hot() function.

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:

This completes the preparation for the formulation.

[1]: K. Takehara, D. Oku, Y. Matsuda, S. Tanaka and N. Togawa, "A Multiple Coefficients Trial Method to Solve Combinatorial Optimization Problems for Simulated-annealing-based Ising Machines," 2019 IEEE 9th International Conference on Consumer Electronics (ICCE-Berlin), Berlin, Germany, 2019, pp. 64-69, doi: 10.1109/ICCE-Berlin47944.2019.8966167.

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.

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.

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:

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

Finally we display the route found above. It can be plotted with the following function: