More Web Proxy on the site http://driver.im/

article

Solution of large-scale symmetric travelling salesman problems

Authors:

Martin Grötschel,

Olaf HollandAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 51, Issue 1-3

Pages 141 - 202

Published: 01 July 1991 Publication History

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.

References

[1]

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).

[2]

H. Crowder and M.W. Padberg, "Solving large-scale symmetric travelling salesman problems to optimality," <i>Management Science</i> 26 (1980) 495-509.

Digital Library

[3]

G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, "Solution of a large scale traveling-salesman problem," <i>Operations Research</i> 2 (1954) 393-410.

[4]

J. Edmonds, "Maximum matching and a polyhedron with 0, 1-vertices," <i>Journal of Research of the National Bureau of Standards B</i> 69 (1965) 125-130.

[5]

W. Felts, P. Krolak and G. Marble, "A man-machine approach toward solving the travelling-salesman-problem," <i>Communications of the ACM</i> 14 (1971) 327-334.

Digital Library

[6]

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.).

[7]

R.E. Gomory and T.C. Hu, "Multi-terminal network flows," <i>Journal of the Society for Industrial and Applied Mathematics</i> 9 (1961) 551-570.

[8]

M. Grötschel, <i>Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme</i> (Hain, Meisenheim am Glan, 1977).

[9]

M. Grötschel and O. Holland, "Solving matching problems with linear programming," <i>Mathematical Programming</i> 33 (1985) 243-259.

Digital Library

[10]

M. Grötschel and O. Holland, "A cutting plane algorithm for minimum perfect 2-matchings," <i>Computing</i> 39 (1987) 327-344.

Digital Library

[11]

M. Grötschel, L. Lovász and A. Schrijver, "The ellipsoid method and its consequences in combinatorial optimization," <i>Combinatorica</i> 1 (1981) 169-197.

[12]

M. Grötschel, L. Lovász and A. Schrijver, <i>Geometric Algorithms and Combinatorial Optimization</i> (Springer, Berlin, 1988).

[13]

M. Grötschel and M. W. Padberg, "On the symmetric travelling salesman problem I: inequalities," <i>Mathematical Programming</i> 16 (1979) 265-280.

[14]

M. Grötschel and M.W. Padberg, "On the symmetric travelling salesman problem II: lifting theorems and facets," <i>Mathematical Programming</i> 16 (1979) 281-302.

[15]

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., <i>The Traveling Salesman Problem</i> (Wiley, Chiehester, 1985) pp. 251-305.

[16]

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., <i>The Traveling Salesman Problem</i> (Wiley, Chichester, 1985) pp. 307-360.

[17]

M. Grötschel and W.R. Pulleyblank, "Clique tree inequalities and the symmetric travelling salesman problem," <i>Mathematics of Operations Research</i> 11 (1986) 537-569.

Digital Library

[18]

M. Held and R.M. Karp, "A dynamic programming approach to sequencing problems," <i>SIAM Journal on Applied Mathematics</i> 10 (1962) 196-210.

[19]

M. Held and R.M. Karp, "The traveling-salesman problem and minimum spanning trees," <i>Operations Research</i> 18 (1970) 1138-1182.

Digital Library

[20]

M. Held and R.M. Karp, "The traveling-salesman problem and minimum spanning trees: part 2," <i>Mathematical Programming</i> 1 (1971) 6-25.

Digital Library

[21]

O. Holland, <i>Sehnittebenenverfahren für Travelling-Salesman- und verwandte Probleme,</i> Doctoral Thesis, University of Bonn (Bonn, 1987).

[22]

R.L. Karg and G.L. Thompson, "A heuristic approach to solving travelling salesman problems," <i>Management Science</i> 10 (1964) 225-247.

Digital Library

[23]

S. Lin and B.W. Kernighan, "An effective heuristic algorithm for the traveling-salesman problem," <i>Operations Research</i> 21 (1973) 498-516.

Digital Library

[24]

M.W. Padberg and M.R. Rao, "Odd minimum cut-sets and b-matchings," <i>Mathematics of Operations Research</i> 7 (1982) 67-80.

Digital Library

[25]

M.W. Padberg and G. Rinaldi, "Optimization of a 532-city symmetric travelling salesman problem by branch and cut," <i>Operations Research Letters</i> 6 (1987) 1-7.

Digital Library

[26]

M.W. Padberg and G. Rinaldi, "An efficient algorithm for the minimum capacity cut problem," <i>Mathematical Programming</i> 47 (1990a) 19-36.

Digital Library

[27]

M.W. Padberg and G. Rinaldi, "Facet identification for the symmetric travelling salesman problem," <i>Mathematical Programming</i> 47 (1990b) 219-257.

Digital Library

[28]

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," <i>Annals of Discrete Mathematics</i> 1 (1977) 479-493.

Cited By

Cook W(2022)Computing in Combinatorial OptimizationComputing and Software Science10.1007/978-3-319-91908-9_3(27-47)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-91908-9_3
Uematsu NUmetani SKawahara Y(2019)An Efficient Branch-and-Cut Algorithm for Approximately Submodular Function Maximization2019 IEEE International Conference on Systems, Man and Cybernetics (SMC)10.1109/SMC.2019.8913989(3160-3167)Online publication date: 6-Oct-2019
https://dl.acm.org/doi/10.1109/SMC.2019.8913989
Silva IGoldbarg Ede Carvalho EGoldbarg M(2017)MO-MAHM: A parallel Multi-agent Architecture for Hybridization of Metaheuristics for multi-objective problems2017 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2017.7969363(580-587)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1109/CEC.2017.7969363
Show More Cited By

Index Terms

Solution of large-scale symmetric travelling salesman problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
      1. Network flows
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
    2. Mathematical optimization
      1. Continuous optimization
        Linear programming

Recommendations

Symmetric Inequalities and Their Composition for Asymmetric Travelling Salesman Polytopes

The Asymmetric Travelling SalesmanATSpolytope ATSPV is the convex hull of incidence vectors of all Hamiltonian circuits in a complete digraph with node set V. This paper studies classes of valid symmetric inequalities ay ≤ a₀ for ATS polytopes with ...
Hamiltonian path and symmetric travelling salesman polytopes

We introduce a projective approach for studying symmetric travelling salesman polytopes (STSPs). Thesymmetric travelling salesman polytope STSP(V) (resp.,Hamiltonian path polytope HP(V)) is the convex hull of incidence vectors of all Hamiltonian cycles (...
On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 51, Issue 1-3

July 1991

408 pages

ISSN:0025-5610

Issue’s Table of Contents

Copyright © Copyright © 1991 The Mathematical Programming Society, Inc.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 1991

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cook W(2022)Computing in Combinatorial OptimizationComputing and Software Science10.1007/978-3-319-91908-9_3(27-47)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-91908-9_3
Uematsu NUmetani SKawahara Y(2019)An Efficient Branch-and-Cut Algorithm for Approximately Submodular Function Maximization2019 IEEE International Conference on Systems, Man and Cybernetics (SMC)10.1109/SMC.2019.8913989(3160-3167)Online publication date: 6-Oct-2019
https://dl.acm.org/doi/10.1109/SMC.2019.8913989
Silva IGoldbarg Ede Carvalho EGoldbarg M(2017)MO-MAHM: A parallel Multi-agent Architecture for Hybridization of Metaheuristics for multi-objective problems2017 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2017.7969363(580-587)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1109/CEC.2017.7969363
Brusco MSteinley D(2015)Affinity Propagation and Uncapacitated Facility Location ProblemsJournal of Classification10.1007/s00357-015-9187-x32:3(443-480)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s00357-015-9187-x
Fischer AFischer FJäger GKeilwagen JMolitor PGrosse I(2014)Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformaticsDiscrete Applied Mathematics10.5555/2747014.2747155166:C(97-114)Online publication date: 31-Mar-2014
https://dl.acm.org/doi/10.5555/2747014.2747155
Manolios PPapavasileiou V(2013)ILP Modulo TheoriesProceedings of the 25th International Conference on Computer Aided Verification - Volume 804410.5555/2958031.2958042(662-677)Online publication date: 13-Jul-2013
https://dl.acm.org/doi/10.5555/2958031.2958042
Aloise DHansen PLiberti L(2012)An improved column generation algorithm for minimum sum-of-squares clusteringMathematical Programming: Series A and B10.5555/3112656.3112875131:1-2(195-220)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.5555/3112656.3112875
Benchimol PHoeve WRégin JRousseau LRueher M(2012)Improved filtering for weighted circuit constraintsConstraints10.1007/s10601-012-9119-x17:3(205-233)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/s10601-012-9119-x
Cook WEspinoza DGoycoolea M(2005)A study of domino-parity and k-parity constraints for the TSPProceedings of the 11th international conference on Integer Programming and Combinatorial Optimization10.1007/11496915_33(452-467)Online publication date: 8-Jun-2005
https://dl.acm.org/doi/10.1007/11496915_33
Bixby R(2002)Solving Real-World Linear ProgramsOperations Research10.5555/2770781.277078450:1(3-15)Online publication date: 1-Feb-2002
https://dl.acm.org/doi/10.5555/2770781.2770784
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents