This paper introduces the 1-tree relaxation of the TSP and the idea of using node weights to improve the bound given by the optimal 1-tree. It is also shown that the best bound that can be obtained in this manner is equal to the optimal value of the subtour linear-programming relaxation of the TSP. Two methods are presented for computing the bound, but neither of them were reported to perform well on computational tests. (The efficient algorithm is given in Held and Karp [1971].)H. Müller-Merbach, Optimale Reihenfolgen, Springer, Berlin.
This book includes a long chapter on the traveling salesman. The treatment covers both exact and heuristic algorithms (including computational tests).
The authors present an analysis of the effectiveness of using the assignment relaxation for the TSP, partially explaining the success earlier algorithms had in solving random asymmetric instances. They propose to use the 2-factor problem as a relaxation for symmetric problems, and tested this idea on random Euclidean problems having up to 20 nodes (using a b-matching code written by Edmonds and Johnson).M. Held and R.M. Karp, "The traveling-salesman problem and minimum spanning trees: part II", Mathematical Programming 1, 6-25.
An efficient iterative method for computing a good 1-tree bound (using node weights) is presented. The authors imbed this in a branch-and-bound algorithm and solve, amongst others, the 42-city instance of Dantzig, Fulkerson, and Johnson [1954], the 57-city instance of Karg and Thompson [1964], and a 64-city random Euclidean instance. These computational results were easily the best reported up to that time.P. Krolak, W. Felts, and G. Marble, "A man-machine approach toward solving the traveling salesman problem", Communications of the ACM 14, 327-334.
A nice paper describing a practical approach to finding good solutions to geometric TSP instances, involving human generated tours, the assignment problem relaxation, node insertion, 2-opt, and a "regional improvement routine" (where the human identifies a region in the current tour that looks suboptimal, and the a subroutine is called to optimize that region and glue it to the full tour).
S. Hong, "A linear programming approach for the traveling salesman problem", Ph.D. Thesis, The Johns Hopkins University.
Hong's thesis was written under the supervision of M. Bellmore. His work is the most significant (computational) contribution to the linear programming approach to the TSP since the original paper of Dantzig, Fulkerson, and Johnson [1954]. The algorithm presented here goes a long way towards automating Dantzig, Fulkerson, and Johnson's method. Hong uses a dual LP algorithm for solving the linear-programming relaxations; the Ford-Fulkerson max-flow algorithm for finding violated subtour inequalities; a heuristic for finding violated blossom inequalities; and a branch-and-bound scheme that includes the addition of subtour inequalities at the nodes of the branch-and-bound tree (such algorithms are now known as "branch-and-cut" (Padberg and Rinaldi [1991])). In short, Hong had most of the ingredients of the current generation of linear-programming based algorithms for the TSP. His computational tests were carried out on random Euclidean instances having up to 20 cities. On the 60 instances that he tests, 59 were solved without branching and the remaining instance required a single branch. Larger instances were not tested due to difficulties with his LP solver. (We thank Leslie Hall for kindly obtaining this manuscript for us at Johns Hopkins University.)H. Steckhan and R. Thome, "Vereinfachungen der Eastmanischeen branch-bound-lösung für symmetrische traveling salesman probleme", Methods of Operations Research 14, 360-389.
Some observations on the branch-and-bound algorithm of Eastman [1958]. Computational results on instances having up to 10 cities are given.
The authors test their version of Held-Karp on the 57-city instance of Karg and Thompson [1964] and a set of instances having with having random edge lengths.M. Held, P. Wolfe, and H.P. Crowder, "Validation of subgradient optimization", Mathematical Programming 6, 62-88.
The iterative algorithm of Held and Karp [1971] is examined in detail. The paper includes some computational results on the 42-city instance of Dantzig, Fulkerson, and Johnson [1954].P.M. Camerini, L. Fratta, and F. Maffioli, "On improving relaxation methods by modified gradient techniques", Mathematical Programming Study3, 26-34.
We were not able to obtain this manuscript.
The author uses a linear programming package written Land and Powell [1973] to implement a branch-and-cut algorithm for the TSP, using subtour inequalities. Computational results for the 42-city instance of Dantzig, Fulkerson, and Johnson [1954], the 48-city instance of Held and Karp [1962], and the 57-city instance of Karg and Thompson [1964].
M. Grötschel, Polyedrische Charackterisierungen kombinatorischer Optimierungsprobleme, Anton Hain Verlag, Meisenheim/Glan.
This is Grötschel's thesis. It contains much of the polyhedral work on the TSP that was carried out jointly with M. Padberg. It also contains the solution of a 120-city instance by means of a cutting-plane algorithm, where cuts (subtour inequalities and comb inequalities) were detected and added by hand to the linear programming relaxation. This demonstrated the power on linear programming approach on an instance significantly larger than the 42-city instance solved by Dantzig, Fulkerson, and Johnson [1954].T.H.C. Smith and G.L. Thompson, "A LIFO implicit enumeration search algorithm for the symmetric traveling salesman problem using Held and Karp's 1-tree relaxation", in: Studies in Integer Programming (P.L. Hammer, E.L. Johnson, B.H. Korte, and G.L. Nemhauser, eds.), Annals of Discrete Mathematics1, North-Holland, Amsterdam, pp. 479-493.
The authors present some improvements to the Held-Karp algorithm, and test their methods on a variety of examples, including the 57-city instance of Karg and Thompson [1964] and a set of ten 60-city random Eucliean instances.
The authors give a short survey of their work on cutting-planes for the TSP and present some computational results that demonstrate the effectiveness of the cutting planes.P. Miliotis, "Using cutting planes to solve the symmetric travelling salesman problem", Mathematical Programming 15, 177-188.
The algorithm uses a combination of subtour cuts and Gomory cuts, similar to the method proposed by Martin [1966]. Tests were made on instances that included the standard 42-city, 48-city, and 57-city examples.
This survey includes algorithms for the TSP and the asymmetric TSP.A. Land, "The solution of some 100-city travelling salesman problems", Technical Report, London School of Economics.
The author describes a cutting-plane algorithm for the TSP. The linear-programming relaxations are solved in integer arithmetic, thus avoiding rounding errors in the computations. The separation algorithms include a shrinking heuristic for identifying subtour inequalities and a heuristic for identifying blossom inequalities (looking at the connected components of the graph obtained by deleting the edges assigned the value 0 or 1 in the solution to the linear-programming relaxation). If no subtours or blossoms are found, a Gomory-cut is added to the relaxation. She uses column generation to handle the great number of edges present in larger instances. The algorithm is tested on ten 100-city random Euclidean instances.