On the symmetric travelling salesman problem: Solution of a 120-city problem
作者： Martin Grötschel
DOI: 10.1007/BFB0120887
关键词:
摘要: The polytope associated with the symmetric travelling salesman problem has been intensively studied recently (cf. [7, 10, 11]). In this note we demonstrate how knowledge of facets can be utilized to solve large-scale problems. particular, report shortest roundtrip through 120 German cities was found using a commercial linear programming code and adding facetial cutting planes in an interactive way.
springer.com
springerlink.com参考文章(15)
Manfred W. Padberg, Saman Hong, On the symmetric travelling salesman problem: A computational study Mathematical Programming Studies. pp. 78- 107 ,(1980) , 10.1007/BFB0120888
Rainer E. Burkard, Travelling Salesman and Assignment Problems: A Survey Annals of discrete mathematics. ,vol. 4, pp. 193- 215 ,(1979) , 10.1016/S0167-5060(08)70827-6
Martin Grötschel, Manfred W. Padberg, On the symmetric travelling salesman problem II: Lifting theorems and facets Mathematical Programming. ,vol. 16, pp. 281- 302 ,(1979) , 10.1007/BF01582117
Jack Edmonds, Matroids and the greedy algorithm Mathematical Programming. ,vol. 1, pp. 127- 136 ,(1971) , 10.1007/BF01584082
M. Grötschel, M. W. Padberg, Lineare Charakterisierungen von Travelling Salesman Problemen Zeitschrift für Operations Research. ,vol. 21, pp. 33- 64 ,(1977) , 10.1007/BF01918456
Martin Grötschel, Manfred W. Padberg, On the symmetric travelling salesman problem I: Inequalities Mathematical Programming. ,vol. 16, pp. 265- 280 ,(1979) , 10.1007/BF01582116
Martin Grötschel, Manfred W. Padberg, Partial linear characterizations of the asymmetric travelling salesman polytope Mathematical Programming. ,vol. 8, pp. 378- 381 ,(1975) , 10.1007/BF01580454
Vašek Chvátal, William Cook, George B. Dantzig, Delbert R. Fulkerson, Selmer M. Johnson, Solution of a Large-Scale Traveling-Salesman Problem Operations Research. ,vol. 2, pp. 7- 28 ,(1954) , 10.1007/978-3-540-68279-0_1
P. Miliotis, Integer programming approaches to the travelling salesman problem Mathematical Programming. ,vol. 10, pp. 367- 378 ,(1976) , 10.1007/BF01580682
Václav Chvátal, Edmonds polytopes and weakly hamiltonian graphs Mathematical Programming. ,vol. 5, pp. 29- 40 ,(1973) , 10.1007/BF01580109