Integer programming approaches to the travelling salesman problem. (English) Zbl 0337.90041


90C10 Integer programming
65K05 Numerical mathematical programming methods
90C05 Linear programming
Full Text: DOI


[1] M. Bellmore and J.C. Malone, ”Pathology of travelling salesman subtour elimination algorithms”,Operations Research 19 (1971) 278–307. · Zbl 0219.90032 · doi:10.1287/opre.19.2.278
[2] M. Bellmore and G.L. Nemhauser, ”The travelling salesman problem: a survey”,Operations Research 16 (1968) 538–558. · Zbl 0213.44604 · doi:10.1287/opre.16.3.538
[3] G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, ”Solution of a large scale travelling salesman problem”,Operations Research 2 (1954) 393–410. · doi:10.1287/opre.2.4.393
[4] G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, ”On a linear programming, combinatorial approach to the travelling salesman problem”,Operations Research 7 (1959) 58–66. · doi:10.1287/opre.7.1.58
[5] W.L. Eastman, ”Linear programming with pattern constraints”, Ph.D. Dissertation, Harvard University, Cambridge, Mass., (1958).
[6] J. Edmonds, ”Maximum matching and a polyhedron with 0, 1-vertices”,Journal of Research of the National Bureau of Standards 69B (1965) 125–130. · Zbl 0141.21802
[7] A.M. Geoffrion and R.E. Marsten, ”Integer programming algorithms: A framework and state-of-the-art survey”,Management Science 18 (1972) 465–491. · Zbl 0238.90043 · doi:10.1287/mnsc.18.9.465
[8] K. Helbig Hansen and J. Krarup, ”Improvements of the Held–Karp algorithm for the symmetric travelling-salesman problem”,Mathematical Programming 7 (1974) 87–96. · Zbl 0285.90055 · doi:10.1007/BF01585505
[9] M. Held and R.M. Karp, ”A dynamic programming approach to sequencing problems”,Journal of the Society for Industrial and Applied Mathematics 10 (1962) 196–210. · Zbl 0106.14103 · doi:10.1137/0110015
[10] M. Held and R.M. Karp, ”The travelling salesman problem and minimum spanning trees, Part II”,Mathematical Programming 1 (1971) 6–25. · Zbl 0232.90038 · doi:10.1007/BF01584070
[11] L.L. Karg and G.L. Thompson, ”A heuristic approach to solving travelling salesman problems”,Management Science 10 (1964) 225–248. · doi:10.1287/mnsc.10.2.225
[12] A. Land and S. Powell,Fortran codes for mathematical programming (Wiley, New York, 1973). · Zbl 0278.68036
[13] J.D. Little, K.G. Murty, D.W. Sweeney and C. Karel, ”An algorithm for the travelling salesman problem”,Operations Research 11 (1963) 972–989. · Zbl 0161.39305 · doi:10.1287/opre.11.6.972
[14] G.T. Martin, ”Solving the travelling salesman problem by integer linear programming”,CEIR, New York (1966).
[15] C.E. Miller, A.W. Tucker and R.A. Zemlin, ”Integer programming formulations and travelling salesman problems”,Journal of the Association for Computing Machinery 7 (1960) 326–329. · Zbl 0100.15101
[16] J.D. Murchland, ”A fixed matrix method for all shortest distances in a directed graph and for the inverse problem”, Ph.D. Dissertation, Karlsruhe (1970). · Zbl 0248.05116
[17] D. Shapiro, ”Algorithms for the solution of optimal cost travelling salesman problem”, Sc.D. Thesis, Washington University, St. Louis, Mo. (1966).
[18] ”Computers in Central Government: Ten Years Ahead”, Civil Service Department,Management Studies 2, HMSO London (1971) (no authors reported).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.