1970
M. Held and R.M. Karp, "The traveling-salesman problem and minimum spanning
trees", Operations Research 18, 1138-1162.
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).
1971
M. Bellmore and J. Malone, "Pathology of traveling-salesman subtour-elimination
algorithms", Operations Research 19, 278-307.
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).
1972
N. Christofides, "Bounds for the travelling-salesman problem", Operations
Research 20, 1044-1056.
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.
1973
S. Lin and B.W. Kernighan, "An effective heuristic algorithm for the traveling-salesman
problem", Operations Research 21, 498-516.
1974
K. Helbig Hansen and J. Krarup, "Improvements of the Held-Karp algorithm
for the symmetric traveling-salesman problem", Mathematical Programming7,
87-96.
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.
1975
W. Schiebel, G. Unger, and J. Terno, "A cutting plane algorithm for the
travelling salesman problem", Report 07-15-76, Sektion Mathematik,
Technische Universität Dresden, GDR.
We were not able to obtain this manuscript.
1976
P. Miliotis, "Integer programming approaches to the travelling salesman
problem", Mathematical Programming 10, 367-378.
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].
1977
M.S. Bazaraa and J.J. Goode, "The traveling salesman problem: a duality
approach", Mathematical Programming 13, 221-237.
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.
1978
M. Grötschel and M. Padberg, "On the symmetric traveling salesman
problem: theory and computation", in: Optimization and Operations Research
(R. Henn, B. Korte, and W. Oettli, eds.), Lecture Notes in Economics
and Mathematical Systems 157, Springer, Berlin, pp. 105-115.
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.
1979
R.E. Burkard, "Travelling salesman and assignment problems: a survey",
in: Discrete Optimization 1 (P.L. Hammer, E.L. Johnson, and B.H.
Korte, eds.), Annals of Discrete Mathematics 4, North-Holland,
Amsterdam, pp. 193-215.
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.
|
