×

zbMATH — the first resource for mathematics

Optimizing over the subtour polytope of the travelling salesman problem. (English) Zbl 0726.90086
The paper is concerned with polyhedral aspects of the symmetric travelling salesman problem. In particular functions related to clique trees [see M. Grötschel and W. Pulleyblank, Math. Oper. Res. 11, 537-569 (1986; Zbl 0626.90060)] are optimized over the subtour polytope S given by the 2-factor and subtour elimination constraints. Further the Chvátal rank of clique tree inequalities is studied. Finally, the structure of the vertices of the polytope S is investigated.
Reviewer: R.E.Burkard (Graz)

MSC:
90C35 Programming involving graphs or networks
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M.L. Balinski, ”On recent developments in integer programming,” in: H.W. Kuhn, ed.,Proceedings of the Princeton Symposium on Mathematical Programming (Princeton University Press, Princeton, NJ, 1970) pp. 267–302. · Zbl 0222.90036
[2] S.C. Boyd and W.R. Pulleyblank, ”Facet generation techniques,” in preparation. · Zbl 1359.90113
[3] N. Christofides, ”The travelling salesman problem,” in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi, eds,Combinatorial Optimization (Wiley, New York, 1979) pp. 131–149. · Zbl 0415.90057
[4] V. Chvátal, ”Edmonds polytopes and a hierarchy of combinatorial problems,”Discrete Mathematics 4 (1973) 305–337. · Zbl 0253.05131 · doi:10.1016/0012-365X(73)90167-2
[5] V. Chvátal, ”Edmonds polytopes and weakly hamiltonian graphs,”Mathematical Programming 5 (1973) 29–40. · Zbl 0267.05118 · doi:10.1007/BF01580109
[6] V. Chvátal, W. Cook and M. Hartmann, ”On cutting plane proofs in combinatorial optimization,” Rutcor Research Report 27–88, Rutgers University (New Brunswick, NJ, 1988). · Zbl 0676.90059
[7] G. Cornuéjols, J. Fonlupt and D. Naddef, ”The traveling salesman problem on a graph and some related integer polyhedra,”Mathematical Programming 33 (1985) 1–27. · Zbl 0562.90095 · doi:10.1007/BF01582008
[8] G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, ”Solutions of a large-scale travelling salesman problem,”Operations Research 2 (1954) 393–410. · doi:10.1287/opre.2.4.393
[9] R.E. Gomory and T.C. Hu, ”Multiterminal network flows,”Journal of SIAM 9 (1961) 551–570. · Zbl 0112.12405
[10] M. Grötschel, ”On the symmetric travelling salesman problem: solution of a 120-city problem,”Mathematical Programming Study 12 (1980) 61–77. · Zbl 0435.90070
[11] M. Grötschel, L. Lovász and A. Schrijver, ”The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197. · Zbl 0492.90056 · doi:10.1007/BF02579273
[12] M. Grötschel and M.W. Padberg, ”On the symmetric travelling salesman problem I: inequalities,”Mathematical Programming 16, (1979) 265–280. · Zbl 0413.90048 · doi:10.1007/BF01582116
[13] M. Grötschel and M.W. Padberg, ”On the symmetric travelling salesman problem II: lifting theorems and facets,”Mathematical Programming 16, (1979) 281–302. · Zbl 0413.90049 · doi:10.1007/BF01582117
[14] M. Grötschel and M. Padberg, ”Polyhedral theory”, in: E. Lawler, J. Lenstra, A. Rinnooy Kan and D. Shmoys, eds.,The Traveling Salesman Problem (Wiley, New York, 1985). · Zbl 0587.90073
[15] M. Grötschel and M. Padberg, ”Polyhedral computations,” in: E. Lawler, J. Lenstra, A. Rinnooy Kan and D. Shmoys, eds.,The Traveling Salesman Problem (Wiley, New York, 1985). · Zbl 0587.90074
[16] M. Grötschel and W.R. Pulleyblank, ”Clique tree inequalities and the symmetric travelling salesman problem,”Mathematics of Operations Research 11 (1986) 537–569. · Zbl 0626.90060 · doi:10.1287/moor.11.4.537
[17] M. Held and R.M. Karp, ”The travelling salesman problem and minimum spanning trees,”Operations Research 18 (1970) 1138–1162. · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[18] R. Karp and C. Papadimitriou, ”On linear characterizations of combinatorial optimization problems,”Proceedings of the Twenty-first Annual Symposium on the Foundations of Computer Science (IEEE Press, New York, 1980) pp. 1–9. · Zbl 0505.65020
[19] M. Katchalski, W. McQuaig and S. Seager, ”Ordered colouring,” Research Report CORR 88-39, Department of Combinatorics and Optimization, University of Waterloo (Waterloo, Ont., 1988).
[20] M.W. Padberg and S. Hong, ”On the symmetric travelling salesman problem: a combinatorial study,”Mathematical Programming Study 12 (1980) 78–107. · Zbl 0435.90071
[21] M. Padberg and L.A. Wolsey, ”Trees and cuts”,Annals of Discrete Mathematics 17 (1983) 511–517. · Zbl 0522.90095
[22] W.R. Pulleyblank, ”Faces of Matching Polyhedra,” Doctoral Thesis, University of Waterloo (Waterloo, Ont., 1973). · Zbl 0318.65027
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.