×

zbMATH — the first resource for mathematics

Using cutting planes to solve the symmetric travelling salesman problem. (English) Zbl 0393.90059

MSC:
90C09 Boolean programming
05C35 Extremal problems in graph theory
05C38 Paths and cycles
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] 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
[3] 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
[4] R. Gomory, ”An algorithm for integer solutions to linear programs”, in: R.L. Graves and P. Wolfe, eds.,Recent advances in mathematical programming (McGraw-Hill, New York, 1963) pp. 269–302. · Zbl 0235.90038
[5] 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
[6] 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
[7] 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
[8] 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
[9] A. Land and S. Powell,Fortran codes for mathematical programming: linear, quadratic and discrete (Wiley, New York, 1973). · Zbl 0278.68036
[10] G.T. Martin, ”An accelerated euclidean algorithm for integer linear programming”, in: R.L. Graves and P. Wolfe, eds.,Recent advances in mathematical programming (McGraw-Hill, New York, 1963) pp. 311–318. · Zbl 0129.34201
[11] G.T. Martin, ”Solving the travelling salesman problem by integer linear programming”,CEIR, New York (1966).
[12] P. Miliotis, ”Integer programming approaches to the travelling salesman problem”,Mathematical Programming 10 (1976) 367–378. · Zbl 0337.90041 · doi:10.1007/BF01580682
[13] P. Miliotis, ”An all-integer arithmetic LP-cutting planes code applied to the travelling salesman problem”, London School of Economics, Department of Operational Research (1975).
[14] 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.