Solving Traveling Salesman Problem with SBM (Simulated Bifurcation Machine)
Introduction
In the previous article, we tried to run the MAX-CUT problem with SBM.
This time, we tried to solve the Traveling Salesman Problem (TSP) with SBM. TSP is often taken up as a concrete example of combinatorial optimization problems.
Traveling Salesman Problem (TSP)
The travelling salesman problem describes a situation when a salesman must find the shortest route to visit N number of cities exactly once and return to the origin city at the end.
If the number of cities is N, there are N! candidate routes, and as N increases, the number of combinations increases exponentially to find the optimal solution by going through all combinations.
We will express this problem in QUBO format and try to solve it with SBM.
Objective function
Create the TSP objective function in QUBO format.
In the method we will use this time, “what number” and “which city” to visit will be one QUBO variable.
For example, in the case of N=4, consider the combination of QUBO variables that will be the route of B→A→C→D. The following table shows the combination of QUBO variables as “what number to visit” as a row and “which city to visit” as a column.
N² variables are required for the number of cities N.
If the distance between cities (i,j) is dᵢ,ⱼ, and the QUBO variable nα,ᵢ is used to express whether or not to visit city i for αth, the objective function is as follows.
The first term represents the total distance you want to minimize, the second and third terms are constraints, and k₁, k₂ are weighting factors that represent the strength of the constraints.
In normal simulated annealing (SA), if the solution obtained satisfies the constraints, the weight on the constraint terms is better to be as small as possible. This is because when moving from one local solution to another, the ease of transfer could be improved further.
This article uses 1/2max(dᵢ,ⱼ) as the weight value.
Although SBM’s algorithm is essentially different from SA, such a scheme may be effective because it uses the same formulation. When we actually tried it, we confirmed that the weight adjustment has an effect on the quality of the solution.
TSPLIB
TSPLIB is one of the benchmark sets for the traveling salesman problem. Problem data can be downloaded from the link.
This time, we evaluated the following two issues. It is a traveling salesman problem in 14 cities and 24 cities respectively.
- burma14
- gr24
Execution with SBM
ISING solver
To solve TSP this time, we use SBM’s ISING solver. ISING solver solves general QUBO model problems. The problem data given by the ISING solver is given as the text data that follows the format called MatrixMarket format for the coefficients of the QUBO polynomial.
%%MatrixMarket matrix coordinate real symmetric
N N E
i0 j0 w_i0j0
i1 j1 w_i1j1
i2 j2 w_i2j2The first line declares that the given matrix is a real symmetric matrix.
The second line describes the matrix dimension NNN and the number of elements EEE. In other words, it corresponds to the number of QUBO variables and their interaction coefficients (non-zero matrix elements) on the Ising machine.
The third and subsequent lines are the matrix element index and value. Only the lower triangular element of the target matrix, that is, i≥ji \geq ji≥j element is specified to be described.
As an example, the data obtained by converting the randomly generated QUBO polynomial of the 6 city problem into a MatrixMarket looks like this.
'%%MatrixMarket matrix coordinate real symmetric
36 36 396
1 1 -1.526
2 1 1.526
2 2 -1.526
3 1 1.526
3 2 1.526
3 3 -1.526
4 1 1.526
4 2 1.526
4 3 1.526
4 4 -1.526
5 1 1.526
5 2 1.526
(Omitted)Execution command
Send the problem data created in the above format with the curl command and try to get the calculation result. Rewrite 192.168.0.1 of the connection destination according to the environment.
curl -i -H "Content-Type: application/octet-stream" -X POST "http://192.168.0.1:8000/solver/ising?steps=500&loops=0&timeout=10&dt=0.2" --data-binary @problem.dataSBM parameters (new parameter supplement)
A new version of SBM PoC edition has been released and the following machine parameters can be set.
dt：Time width when solving differential equations with symplectic Euler method.- Δt of (12) and (13) formula in SBM paper.
C：Constants that compose the SBM Hamiltonian.- ξ₀ of (2) formula in SBM paper.
The default value of dt is 1.0 and C is automatically adjusted by default, but depending on the problem, setting these values appropriately may make it easier to obtain a better solution. This time, we tried to find the optimal setting value of dt and C.
I also tried several settings for steps.
Execution result
Adjusting parameter dt
We changed dt in the range of 0.01 to 1.0 and calculated the distance of the TSP path from the obtained QUBO variable value.
Other machine parameter settings are as follows:
-steps: 100, 1000, 10000 -loops: 0 (automatic setting) -target: known optimal value -timeout: 10 (burma14), 20 (gr24) -C: 0 (automatic setting)
burma14
The figure above is a graph with the horizontal axis plotted as dt and the vertical axis as distance. The lower end of the vertical axis is the optimal value (3323).
In the 14 city problem burma14, we were able to reach an optimal solution in the range of execution. In particular, it shows that an optimal solution is easily obtained in the region of 0.1<dt<0.3.
gr24
Since the problem data of gr24 is only a distance matrix and no city location is given, the route map could not be output.
In gr24, we tried 10 times for eachdt and examined its mean and standard deviation. The figure plots the average value of the TSP solution distance, with the standard deviation as the error bar. The lower end of the vertical axis is also the optimum value (1272).
In the domain of dt> 0.5, no feasible solution for TSP was obtained.
Compared to the results for each steps in the region of 0.1<dt<0.3, the difference from the optimal solution is smaller at steps=10000. For steps, there was a tendency for better solutions to be obtained if a relatively large value was set.
When the execution time limit is fixed, steps andruns are in a trade-off relationship, so setting the optimal steps may make it easier to obtain an accurate solution.
When the execution time limit is fixed, steps andruns are in a trade-off relationship, so setting the optimal steps may make it easier to obtain an accurate solution.
Adjusting parameter C
We tried various setting values for C, another parameter added in the new version.
First, check the automatic setting value of C in the previousdt experiment.
In the figure, the average of the automatically set value of C is calculated and plotted from the execution results of 10 times for each dt. It turned out that the value of 0.0020~0.0022 was well set up around 0.00175 until dt=0.3 and below.
Therefore, I took a value in increments of 0.00025 in the range of 0.00025~0.005, and executed it 10 times as before. The parameters other than C are set to the setting values (steps=10000, dt=0.26) that obtained an average good solution in the previous section.
The result of C=0.00150, which is a little smaller than the setting value in the automatic adjustment, is good for both the average value and the minimum value and has reached the optimal solution. Also, no executable solution was obtained with C=0.003 or higher.
It turns out that the adjustment of C may also contribute to improving the solution.
Summary
The TSP problem and the best result obtained are shown below.
It turned out that a solution close to the optimal solution of TSP can be obtained by adjusting various machine parameters of steps, dt, and C. In addition, in the problem dealt with this time, there was a tendency that a relatively good solution was easily obtained by adjusting in the range of 0.2<dt<0.4.
