The traveling salesman problem on a graph and some related integer polyhedra.(English)Zbl 0562.90095
Given a graph \(G=(N,E)\) and a length function l:E\(\to {\mathbb{R}}\), the graphical traveling salesma problem is that of finding a minimum length cycle going at least once through each node of G. This formulation has advantages over the traditional formulation where each node must be visited exactly once. We give some facet inducing inequalities of the convex hull of the solutions to that problem. In particular, the so- called comb inequalities of Grötschel and Padberg are generalized. Some related integer polyhedra are also investigated. Finally, an efficient algorithm is given when G is a series-parallel graph.
MSC:
| 90C35 | Programming involving graphs or networks |
| 52Bxx | Polytopes and polyhedra |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 90C10 | Integer programming |
Keywords:
graphical traveling Salesman;minimum length cycle;facet;comb inequalities;integer polyhedra;efficient algorithm;Steiner tree;polynomial algorithm;series-parallel graphCite
Full Text:DOI
References:
| [1] | J.A. Bondy and U.S.R. Murty,Graph theory with applications (North-Holland, Amsterdam, 1976). ·Zbl 1226.05083 |
| [2] | G. Cornuéjols, D. Naddef and W.R. Pulleyblank, ”Halin graphs and the travelling salesman problem”,Mathematical Programming 26 (1983) 287–294. ·Zbl 0506.90083 ·doi:10.1007/BF02591867 |
| [3] | J. Edmonds, ”Matroids and the greedy algorithm”,Mathematical Programming 1 (1971) 127–136. ·Zbl 0253.90027 ·doi:10.1007/BF01584082 |
| [4] | B. Fleischmann, ”Linear programming approaches to travelling salesman and vehicle scheduling problems”, Technical Report, Universität Hamburg (paper presented at the XI. International Symposium on Mathematical Programming, Bonn, 1982). |
| [5] | B. Fleischmann, ”A new class of cutting planes for the symmetric travelling salesman problem”, Report No. QM-03-83, Institut für Unternehmensforschung, Universität Hamburg (1983). ·Zbl 0652.90072 |
| [6] | G.N. Frederikson and J. Jager, ”On the relationship between biconnectivity and travelling salesman problems”,Theoretical Computer Science 19 (1982) 189–201. ·Zbl 0486.90082 ·doi:10.1016/0304-3975(82)90059-7 |
| [7] | M. Grötschel and M.W. Padberg, ”On the symmetric travelling salesman problem I, II”,Mathematical Programming 16 (1979) 265–302. ·Zbl 0413.90048 ·doi:10.1007/BF01582116 |
| [8] | W. Pulleyblank, ”Faces of matching polyhedra”, Ph.D. Thesis, University of Waterloo (Waterloo, Ontario, 1973). ·Zbl 0318.65027 |
| [9] | D. M. Ratliff and A.S. Rosenthal, ”Order-picking in a rectangular warehouse: A solvable case of the travelling salesman problem”,Operations Research 31 (1983) 507–521. ·Zbl 0523.90060 ·doi:10.1287/opre.31.3.507 |
| [10] | K. Takamizawa, T. Nishizeki and N. Saito, ”Linear time computability of combinatorial problems on series-parallel graphs”,Journal of the ACM 29 (1982) 632–641. ·Zbl 0485.68055 ·doi:10.1145/322326.322328 |
| [11] | J.A. Wald and C.J. Colbourn, ”Steiner trees, partial 2-trees and minimum IFI methods”,Networks 13 (1983) 159–167. ·Zbl 0529.68036 ·doi:10.1002/net.3230130202 |
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.
