Facet identification for the symmetric traveling salesman polytope
作者： Manfred Padberg , Giovanni Rinaldi
DOI: 10.1007/BF01580861
关键词:
摘要: Several procedures for the identification of facet inducing inequalities symmetric traveling salesman polytope are given. An procedure accepts as input support graph a point which does not belong to polytope, and returns output some violated by point. A always accomplishes this task is calledexact, otherwise it calledheuristic. We give exact subtour elimination 2-matching constraints, based on Gomory—Hu Padberg—Rao algorithms respectively. Efficient reduction proposed accelerate these two substantially. Exact heuristic shrinking conditions also given that yield efficient simple general comb elementary clique tree inequalities. These constitute core polytopal cutting plane algorithm we have devised programmed solve substantial number large-scale problem instances with sizes up 2392 nodes optimality.
springer.com
sci-hub.se 参考文章(21)
Manfred W. Padberg, Saman Hong, On the symmetric travelling salesman problem: A computational study Mathematical Programming Studies. pp. 78- 107 ,(1980) , 10.1007/BFB0120888
David Shmoys, Eugene L. Lawler, Alexander H. G. Rinnooy Kan, Jan Karel Lenstra, The traveling salesman problem ,(1985)
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
Martin Grötschel, Olaf Holland, A cutting plane algorithm for minimum perfect 2-matchings Computing. ,vol. 39, pp. 327- 344 ,(1987) , 10.1007/BF02239975
J.P. Secrétan, Der Saccus endolymphaticus bei Entzündungsprozessen ORL. ,vol. 6, pp. 1- 29 ,(1944) , 10.1159/000273299
Patrick Krolak, Wayne Felts, George Marble, A man-machine approach toward solving the traveling salesman problem Communications of the ACM. ,vol. 14, pp. 327- 334 ,(1971) , 10.1145/362588.362593
M. Padberg, G. Rinaldi, An efficient algorithm for the minimum capacity cut problem Mathematical Programming. ,vol. 47, pp. 19- 36 ,(1990) , 10.1007/BF01580850
Francisco Barahona, Michele Conforti, A construction for binary matroids Discrete Mathematics. ,vol. 66, pp. 213- 218 ,(1987) , 10.1016/0012-365X(87)90097-5
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization Combinatorica. ,vol. 1, pp. 169- 197 ,(1981) , 10.1007/BF02579273
H. Weyl, Elementare Theorie der konvexen Polyeder Commentarii Mathematici Helvetici. ,vol. 7, pp. 290- 306 ,(1934) , 10.1007/BF01292722