|
|
 |
| TSP Annotated Bibliography |
 |
|
1980
H. Crowder and M.W. Padberg, "Solving large-scale symmetric travelling
salesman problems to optimality", Management Science 26, 495-509.
This work improves on the earlier study of Padberg
and Hong [1980], including the addition of further rounds of cutting planes.
The IBM MPSX-MIP/370 integer-programming solver is used to carry out a
branch-and-bound search on the final linear programming relaxation. If
the integral solution found by this search is not a tour, then the subtour
inequalities violated by the solution are added to the relaxation and branch-and-bound
is called again. The computational results obtained in this study are very
impressive, including the solution of a 318-city instance described in
Lin and Kernighan [1973]. This 318-city instance would remain until 1987
as the largest TSP solved.
M. Grötschel, "On the symmetric travelling salesman problem: solution
of a 120-city problem", Mathematical Programming Study 12,
61-77.
This is a journal version of the computational
study described in Grötschel [1977]. It is very impressive that this
120-city instance could be so with the addition of so few cutting planes.
D.J. Houck, Jr., J.C. Picard, M. Queyranne, and R.R. Vemuganti, "The travelling
salesman problem as a constrained shortest path problem: theory and computational
experience", OPSEARCH 17, 93-109.
M.W. Padberg and S. Hong, "On the symmetric travelling salesman problem:
a computational study", Mathematical Programming Study 12, 78-107.
A cutting-plane algorithm is described. The algorithm
makes use of new separation routines for comb inequalities. Like Land [1979],
the linear programming computations were carried out using integer arithmetic
to "avoid any problems connected with round-off errors." In their computational
study, 54 out of total of 74 instances were solved by the linear programming
relaxation. For the 318-city example of Lin and Kernighan [1973], the bound
obtained via the relaxation was within a factor of 0.96 of the best tour
that was found.
1982
J. Mohan, "A study in parallel computation - the traveling salesman problem",
Technical Report CMU-CS-82-136, Computer Science Department, Carnegie
Mellon University, 1982.
We do no have a copy of this manuscript.
T. Volgenant and R. Jonker, "A branch and bound algorithm for the symmetric
traveling salesman problem based on the 1-tree relaxation", European
Journal of Operational Research 9, 83-89.
A variation of the Held-Karp algorithm is described,
together with computational results for a number of small instances, including
the ten 60-city examples of Smith and Thompson [1977].
1983
B. Gavish and K.N. Srikanth, "Algorithms for solving large-scale symmetric
traveling salesman problems to optimality", Working Paper Series Number
QM8329, Graduate School of Management, University of Rochester.
We do not have a copy of this manuscript.
T. Volgenant and R. Jonker, "The symmetric traveling salesman problem and
edge exchanges in minimal 1-trees", European Journal of Operational
Research 12, 394-403.
1984
R. Jonker and T. Volgenant, "Nonoptimal edges for the symmetric traveling
salesman problem", Operations Research 32, 837-846.
1985
B. Fleischmann, "A cutting plane procedure for the travelling salesman
problem on road networks", European Journal of Operational Research
21,
307-317.
A linear-programming relaxation is built using
TSP-specific cuts described in the paper. If no such cut is found, then
a Gomory-cut will be added. Computational results are given for a number
of TSP instances from the literature (including the 120-city example of
Grötschel [1977]).
1987
O.A. Holland, "Schnittebenenverfahren für travelling-salesman und
verwandte probleme", Dotoral Thesis, Universität Bonn.
M. Grötschel and O. Holland, "A cutting plane algorithm for minimum
perfect 2-matchings", Computing 39, 327-344.
M. Padberg and G. Rinaldi, "Optimization of a 532-city symmetric traveling
salesman problem by branch and cut", Operations Research Letters6,
1-7.
1988
G. Carpaneto, M. Fischetti, and P. Toth, "New lower bounds for the symmetric
travelling salesman problem", Mathematical Programming 45,
223-254.
1989
J. Rost and E. Maehle, "Implementation of a parallel branch-and-bound algorithm
for the travelling salesman problem", in: CONPAR 88: Proceedings,
(C.R. Jesshop and K.D. Reimartz, eds.), The British Computer Society
Workshop Series, Cambridge University Press, New York, pp. 152-159.
We do not have a copy of this paper.
|
|
|
