An Exact Ranked Linear Assignments Solution to the Symmetric Traveling Salesman Problem

Roy Danchick

Independent Researcher, 2051 S. Bentley Ave., Apt. 301, Los Angeles, CA, USA.

DOI: 10.4236/oalib.1106159                

Abstract

In this paper, we show how Murty’s ranked linear assignment algorithm can be applied to exactly solve the symmetric Traveling Salesman Problem (TSP). To increase the Murty algorithm’s computational efficiency in solving the TSP, we develop a simple algorithm that determines whether a node that is generated in Murty’s sequential node partitioning process contains a sub-cycle of length less than n, where n is the number of cities to be visited. Each such node cannot generate a genuine solution, which must be a full n-cycle, and can thus be eliminated from further partitioning. In exactly, solving the TSP Murty’s ranking process continues, discarding all such nodes, terminating in a finite number of rankings when the first such ranked solution is encountered that is a full n-cycle. This first ranked n-cycle is the exact solution to the given TSP problem.

Keywords

Traveling Salesman, Applied Probability, Assignment

1. Introduction

The NP-hard Traveling Salesman Problem (TSP) is a paradigm of computational complexity. It continues to be one of the most intensively investigated problems in Operations Research. The famed Irish mathematician William Rowan Hamilton first formulated the TSP problem in the 1800’s. Merrill Flood, the American mathematician, popularized the TSP as a worthy object for investigation in the 1940’s [1] . The Rand Corporation, in the 1950’s was a focal point for research on the TSP. At Rand Richard Bellman, George Dantzig, Ray Fulkerson and Selmer Johnson made fundamental contributions to the solution of the TSP. Bellman in [2] proposed a dynamic programming approach to solving the TSP that was limited to a small number of cities. Bellmans’s algorithm was rediscovered and improved by Held and Karp in [3] . Their approach provides both sharp bounds for the solution as well as the computational complexity for attaining an approximate solution and was able to find an exact solution for the TSP problem of 64 cities.

Bellman’s and the Held-Karp’s algorithms are based on a branch and bound approach. The branch and bound approach is based on the principle that the total set of feasible solutions can be partitioned into smaller subsets of solutions. Branch and bound-based TSP algorithms are not exact. Mathematicians and Computer Scientists have since worked to improve their computational efficiency, even at the margins, of the best available of these algorithms. Gutin and Punnin summarized the state of the art of TSP algorithms as of 20,002 in [4] . The record for the solved-for number of cities is 85,900 at Bell laboratories in 2006.

Branch-and-cut is a second general technique to solve the symmetric TSP problem. It requires an exponential number of cut-set elimination constraints. David P. Williams has compiled a very accessible overview of progress on the TSP in [5] which includes a section on branch and cut methods in conjunction with linear programming algorithms. To complete the picture, there is an extensive literature on heuristic TSP solvers [6] .

In this paper, we adapt Murty’s ranked linear assignment algorithm [7] to the symmetric TSP application. The Murty algorithm solves the ranked linear assignment problem in a sequence of stages. In the first stage, it uses, say, the Jonker-Volgenant (JV) [8] fast 0 - 1 integer linear assignment algorithm to find the exact minimizing solution on the original assignment problem matrix. The first stage solution then generates a set of n nodes from the initial solution by partitioning this first stage solution. Each such node specifies which matrix elements in the first stage solution are to be included in the next solution and which are to be excluded. For each node, the included elements specify which rows and columns are to be struck out of the original first stage matrix to provide the assignment matrices in the next stage while the excluded elements specify which elements in the original matrix are to be replaced by machine infinity. This produces a set of node-correspondent square matrices of decreasing order. Each such node-specific matrix is subjected to the JV algorithm thus producing an assignment value; the smallest of these values is then the second ranked value. The method proceeds recursively from one stage to the next to generate the third ranked solution, the fourth, etc. Our TSP-specific implementation continues the ranking until the first full n-cycle is found, thus making our proposed algorithm exact.

To further adapt the Murty ranked linear assignment algorithm to the TSP for computational efficiency, we construct a simple algorithm that determines whether a node contains a sub-cycle of length < n. Such nodes cannot generate a full cycle. We will show that most nodes contain sub-cycles of length $l,2\le l<n$ . We can thus expect that the Murty algorithm, equipped with this node sub-cycle identification and elimination algorithm along with a core fast JV 0 - 1 integer linear assignment problem solution algorithm, which is $O\left(r^3\right)$ in complexity, $2\le r\le n$ , will compare well in speed with the currently best available symmetric TSP algorithms but in contrast with them always provide exact answers.

We assume the assignment matrix of distances between the cities to be visited is symmetric and positive except for zeros along the main diagonal. We use the device of replacement of each diagonal zero entry with a positive number that is greater than any other matrix entry. This trick guarantees that no ranked solution contains a 1-cycle. Importantly we show that eliminating all such permutations containing a 1-cycle asymptotically shrinks the number of possible permutations that must be processed by Murty’s ranked linear assignment algorithm by a factor of ≈0.6321. The sub-cycle node elimination algorithm removes the remaining $0.3679\left(1-1/n\right)n!$ possible permutations as $n\to \infty$ . The space of solutions is thus reduced to the set of $\left(n-1\right)!$ full n-cycles.

Section 2 Contains our definitions and notation.

Section 3. Provides our key proofs and a computational example

Section 4. Supplies our conclusions

Section 5. Sketches a map for future research.

Section 6. Lists references.

2. Definitions and Notation

We closely follow the definitions and notation found in [7] in which:

n = the number of cities along the traveling salesman’s route.

$C={\left(c_{ij}\right)}_{i,j=1,2,\cdots ,n}$ is the assignment matrix of inter-city distances such that $c_{ij}=c_{ji}>0,i\ne j,c_{ii}=d>c_{ij},i,j\le 1,2,\cdots ,n$ .

Paraphrasing Murty in [7] and specializing the general ranked assignment problem down to the TSP we can define it as the 0 - 1 integer linear programming problem with an additional full n-cycle constraint (4):

Minimize $Z={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_{ij}}}{x}_{ij}$

Subject to: 1) ${\displaystyle \underset{j=1}{\overset{n}{\sum }}{x}_{ij}}=1,i=1,2,\cdots ,n$ (1)

2) ${\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ij}}=1,j=1,2,\cdots ,n$

3) $x_{ij}=1\text{or}{x}_{ij}=0,i,j=1,2,\cdots ,n$

4) If $\left(1,j_1\right),\left(2,j_2\right),\cdots ,\left(n,j_n\right)$ are the indices of the variables $x_{ij}$ taking on the value 1 then the corresponding group element that is contained in the symmetric group of permutations on n letters, $S_n$ , is a full cycle of length n.

A node, M, that is generated on the k^th stage of the ranking process is given by:

$M=\left\{\left(i_1,j_1\right),\left(i_2,j_2\right),\cdots ,\left(i_r,j_r\right);\overline{\left(m_1,p_1\right)},\overline{\left(m_2,p_2\right)},\cdots ,\overline{\left(m_{n-r},p_{n-r}\right)}\right\},$

$\left(i_1,j_1\right),\left(i_2,j_2\right),\cdots ,\left(i_r,j_r\right)$ specify which original matrix entries are to retained in the solution and $\overline{\left(m_1,p_1\right)},\overline{\left(m_2,p_2\right)},\cdots ,\overline{\left(m_{n-r},p_{n-r}\right)}$ specify which original matrix entries are to be excluded from the solution by inserting machine ∞ into the entries $\left(m_i,p_i\right),i=1,2,\cdots ,n-r,r<n$ .

3. Derivations

3.1. Node Rejection and Solution Identification

The basic idea is to sequentially form the node-correspondent product of 2-cycles, $\left(i_1,j_1\right),\left(i_2,j_2\right),\cdots ,\left(i_r,j_r\right)\in S_r$ , into a product of disjoint cycles. A necessary condition for the node to generate a genuine solution to the TSP is that this product must not contain a single cycle of length ≤ r. We have constructed a simple algorithm to determine whether this necessary condition is met. It requires $O\left(r^2\right)$ integer comparisons. The MATLAB code implementation of this algorithm is shown below. The input variables are defined as the integer vectors:

$\begin{array}{l}I=\left[i_1,i_2,\cdots ,i_r\right]\\ J=\left[j_1,j_2,\cdots ,j_r\right]\end{array}$

The output variable is: $\text{test}=\{\begin{array}{l}\text{0 if the node does not contain a sub-cycle}\\ \text{1 if the node contains a sub-cycle}\end{array}$ .

An important consequence of sub-cycle identification and rejection is that the node partitioning process for a given ranked assignment solution stops whenever a sub-cycle is encountered. The same algorithm can be exploited to determine whether a node-partitioning solution is a genuine n-cycle and is a solution candidate, depending on whether its Z value is smallest among those from the set of eligible nodes―those whose two-cycle products do not contain sub-cycles in their representation as products of disjoint sub-cycles.

3.2. Diagonal ∞’s and Node Elimination Algorithm Probabilities and Statistics

The efficiency advantage that the Murty ranked assignment approach confers to the TSP problem derives from two essential features: 1) The large fraction of the $n!$ possible permutation solutions that are eliminated by the machine ∞’s main diagonal entries and 2) the elimination of candidate nodes by the node rejection algorithm.

Table 1 below shows the number of permutations that keep at least 1 of the n letters fixed and are thus eliminated by the node identification and rejection algorithm. Table 2 shows the result of a set of Monte Carlo sampling experiments with a sample number of 1000 per each case of the number of cities.

Examination of Table 1 motivates the key ansatz:

The number of permutations, $R_n$ , eliminated because of diagonal ∞’s is given by the recursion:

Table 1. Diagonal ∞ permutation elimination.

Table 2. Node rejection fractions.

$R_n=\{\begin{array}{l}n{R}_{n-1}-1\text{if n is even}\\ n{R}_{n-1}+1\text{if n is odd}\end{array},n=3,4,5,\cdots$ (2)

If (2) holds for all $n\ge 3$ then the corresponding diagonal ∞’s permutation rejection probability recursion is given by:

$p_n=\{\begin{array}{l}{p}_{n-1}-1/n!\text{if n is even}\\ p_{n-1}+1/n!\text{if n is odd}\end{array},n=3,4,5,\cdots$ (3)

If the recursion (2) above holds for all $n\ge 3$ we can expand recursion (3) to obtain

$p_{n+1}=p_2+{\displaystyle \underset{k=3}{\overset{n}{\sum }}{\left(-1\right)}^{i-1}/k!}$ (4)

From (4) it is easy to see that

$\underset{n\to \infty }{\lim }{p}_n=1-\exp \left(-1\right)\approx 0.6321$ (5)

which is agreement with what Table 1 and Table 2 show.

We will use the four California cities: 1) Los Angeles, 2) San Diego, 3) San Jose, and 4) San Francisco, to pose a “toy problem” that nevertheless captures the essential features and potential effectiveness of our approach. The corresponding assignment matrix, with entries rounded to the nearest mile, is:

$C=\left[\begin{array}{cccc}\infty & 120& 340& 382\\ 120& \infty & 466& 508\\ 340& 466& \infty & 48\\ 382& 508& 48& \infty \end{array}\right]$

By inspection the optimal stage 1 solution is:

$\left(1,2\right),\left(2,1\right),\left(3,4\right),\left(4,3\right),Z=336.$

Note that this stage 1 solution is not a solution of the TSP problem because it contains two sub-cycles of length 2.

The stage 2 nodes that are partitioned by the optimal solution of stage 1 are:

$\begin{array}{l}{M}_1=\overline{\left(1,2\right)},\\ M_2=\left(1,2\right),\overline{\left(2,1\right)},\\ M_3=\left(1,2\right),\left(2,1\right),\overline{\left(3,4\right)},\\ M_4=\left(1,2\right),\left(2,1\right),\left(3,4\right),\overline{\left(4,3\right)}.\end{array}$

The node rejection test tells us that only $M_1$ and $M_2$ need be processed.

The optimal stage 2 solution on $M_1$ is the 4-cycle: $\left(1,4\right),\left(4,3\right),\left(3,2\right),\left(2,1\right),Z=966$

The optimal stage 2 solution on $M_2$ is the 4-cycle $\left(1,2\right),\left(2,3\right),\left(3,4\right),\left(4,1\right),Z=1010$ .

Thus the solution to the given TSP problem is the solution is on $M_1$ .

4. Conclusions

We have proposed an exact algorithm for the solution the symmetric traveling salesman problem that exploits Murty’s ranked linear assignment algorithm. We have shown how the Murty algorithm can be equipped with a simple test that eliminates from further processing any node that cannot generate a full n-cycle. We have proved that if the recursion (2) holds that the device of inserting machine ∞’s down the main diagonal asymptotically reduces the number of candidate permutations by a factor of $1-\exp \left(-1\right)\approx 0.6321$ . The remaining $0.3679\left(1-1/n\right)n!$ permutations, each of which corresponds to a sub-cycles of length < n, are eliminated by the node rejection test. Exploiting the fast JV algorithm as the core 0 - 1 integer linear assignment problem solution method gives the proposed algorithm the potential for great efficiency in exactly solving large problems with $n\gg 1$ .

5. Directions for Future Research

Our first objective would be to prove the conjecture that the recursion (2) holds for all $n\ge 3$ , say, by mathematical induction.

Second would be the derivation of the computational complexity of our proposed algorithm.

Finally, we would either acquire reliable Murty and JV codes or program them from scratch, equip the Murty code with the node rejection algorithm and run the Murty + JV + node rejection combination on sample problems in the literature. We would then compare run times for our proposed algorithm with those of the best current symmetric TSP codes.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Flood, M. (1956) The Traveling-Salesman Problem. Operations Research, 4, 61-75. https://doi.org/10.1287/opre.4.1.61
[2]	Bellman, R. (1962) Dynamic Programming Treatment of the Traveling Salesman Problem. Journal of the ACM, 9, 61-63. https://doi.org/10.1145/321105.321111
[3]	Held, M. and Karp, R. (1962) A Dynamic Programming Approach to Sequencing. Journal for the Society for Industrial and Applied Mathematics, 10, 1-10. https://doi.org/10.1137/0110015
[4]	Gutin, G. and Punnen, E. (2002) The Traveling Salesman Problem and Its Variation. Vol. 12, Springer, New York.
[5]	Williamson, D. (2014) The Traveling Salesman Problem: An Overview. Lecture Notes, Cornell University Ebay Research, 21 January.
[6]	Rego, C., Gamboa, D., Glover, F. and Osterman, C. (2011) Traveling Salesman Problem Heuristics: Leading Methods, Implementations and Latest Advances. European Journal of Operational Research, 211, 427-441. https://doi.org/10.1016/j.ejor.2010.09.010
[7]	Murty, K. (1968) An Algorithm for Ranking All the Assignments in Order of Increasing Cost. Operations Research, 16, 682-687. https://doi.org/10.1287/opre.16.3.682
[8]	Jonker, R. and Volgenant, A. (1987) A Shortest Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing, 38, 325-340. https://doi.org/10.1007/BF02278710