Abstract
We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours.
In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.
References
E. Balas, and M.W. Padberg: “On the facial structure of the travelling salesman polytope”, Carnegie-Mellon University, Pittsburgh, U.S.A., (April, 1973), unpublished.
V. Chvatal, “Edmonds polytopes and weekly hamiltonian graphs”,Mathematical Programming 5 (1973) 29–40.
G. Dantzig, R. Fulkerson and S. Johnson: “Solution of a large-scale travelling-salesman problem”,Operations Research 2 (1954) 393–410.
R. Garfinkel, and G.L. Nemhauser,Integer programming (Wiley, New York, 1972).
M. Grotschel and M.W. Padberg, “Lineare Charakterisierungen von Travelling Salesman Problemen”,Zeitschrift fur Operations Research, to appear.
I. Heller, “On the problem of shortest path between points”, I and II,Bulletin of the American Mathematical Society 59 (1953) 551–552 (abstract).
H.W. Kuhn, “On certain convex polyhedra”,Bulletin of the American Mathematical Society 61 (1955) 557–558 (abstract).
M.W. Padberg and M.R. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”,Mathematical Programming 7 (1974) 32–45.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Grötschel, M., Padberg, M.W. Partial linear characterizations of the asymmetric travelling salesman polytope. Mathematical Programming 8, 378–381 (1975). https://doi.org/10.1007/BF01580454
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580454