Abstract
In this paper we report on a cutting plane procedure with which we solved symmetric travelling salesman problems of up to 1000 cities to optimality. Our implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope. We describe the important ingredients of our code and give an extensive documentation of its computational performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.E. Bland and D.F. Shallcross, “Large travelling salesman problems arising from experiments in X-ray crystallography: a preliminary report on computation,” Technical Report No. 730, School of OR/IE, Cornell University (Ithaca, NY, 1987).
H. Crowder and M.W. Padberg, “Solving large-scale symmetric travelling salesman problems to optimality,”Management Science 26 (1980) 495–509.
G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, “Solution of a large scale traveling-salesman problem,”Operations Research 2 (1954) 393–410.
J. Edmonds, “Maximum matching and a polyhedron with 0, 1-vertices,”Journal of Research of the National Bureau of Standards B 69 (1965) 125–130.
W. Felts, P. Krolak and G. Marble, “A man-machine approach toward solving the travelling-salesman-problem,”Communications of the ACM 14 (1971) 327–334.
F. Glover, D. Klingman, J. Mote and D. Whitman, “A primal simplex variant for the maximum flow problem,” Center of Cybernetic Studies, CCS 362 (Austin, TX, n.d.).
R.E. Gomory and T.C. Hu, “Multi-terminal network flows,”Journal of the Society for Industrial and Applied Mathematics 9 (1961) 551–570.
M. Grötschel,Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme (Hain, Meisenheim am Glan, 1977).
M. Grötschel and O. Holland, “Solving matching problems with linear programming,”Mathematical Programming 33 (1985) 243–259.
M. Grötschel and O. Holland, “A cutting plane algorithm for minimum perfect 2-matchings,”Computing 39 (1987) 327–344.
M. Grötschel, L. Lovász and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197.
M. Grötschel, L. Lovász and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988).
M. Grötschel and M. W. Padberg, “On the symmetric travelling salesman problem I: inequalities,”Mathematical Programming 16 (1979) 265–280.
M. Grötschel and M.W. Padberg, “On the symmetric travelling salesman problem II: lifting theorems and facets,”Mathematical Programming 16 (1979) 281–302.
M. Grötschel and M.W. Padberg, “Polyhedral theory,” in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D. Shmoys, eds.,The Traveling Salesman Problem (Wiley, Chichester, 1985) pp. 251–305.
M.W. Padberg and M. Grötschel, “Polyhedral computations,” in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D. Shmoys, eds.,The Traveling Salesman Problem (Wiley, Chichester, 1985) pp. 307–360.
M. Grötschel and W.R. Pulleyblank, “Clique tree inequalities and the symmetric travelling salesman problem,”Mathematics of Operations Research 11 (1986) 537–569.
M. Held and R.M. Karp, “A dynamic programming approach to sequencing problems,”SIAM Journal on Applied Mathematics 10 (1962) 196–210.
M. Held and R.M. Karp, “The traveling-salesman problem and minimum spanning trees,”Operations Research 18 (1970) 1138–1182.
M. Held and R.M. Karp, “The traveling-salesman problem and minimum spanning trees: part 2,”Mathematical Programming 1 (1971) 6–25.
O. Holland,Schnittebenenverfahren für Travelling-Salesman- und verwandte Probleme, Doctoral Thesis, University of Bonn (Bonn, 1987).
R.L. Karg and G.L. Thompson, “A heuristic approach to solving travelling salesman problems,”Management Science 10 (1964) 225–247.
S. Lin and B.W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,”Operations Research 21 (1973) 498–516.
M.W. Padberg and M.R. Rao, “Odd minimum cut-sets andb-matchings,”Mathematics of Operations Research 7 (1982) 67–80.
M.W. Padberg and G. Rinaldi, “Optimization of a 532-city symmetric travelling salesman problem by branch and cut,”Operations Research Letters 6 (1987) 1–7.
M.W. Padberg and G. Rinaldi, “An efficient algorithm for the minimum capacity cut problem,”Mathematical Programming 47 (1990a) 19–36.
M.W. Padberg and G. Rinaldi, “Facet identification for the symmetric travelling salesman problem,”Mathematical Programming 47 (1990b) 219–257.
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,”Annals of Discrete Mathematics 1 (1977) 479–493.
Author information
Authors and Affiliations
Additional information
Supported by DFG-Schwerpunkt “Anwendungsbezogene Optimierung und Steuerung” Universität Augsburg, Germany.
Supported by SFB 303 (DFG), Forschungsinstitut für Diskrete Mathematik, Institut für Operations Research, Universität Bonn, Germany.
Rights and permissions
About this article
Cite this article
Grötschel, M., Holland, O. Solution of large-scale symmetric travelling salesman problems. Mathematical Programming 51, 141–202 (1991). https://doi.org/10.1007/BF01586932
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01586932