Facet identification for the symmetric traveling salesman polytope

Several procedures for the identification of facet inducing inequalities for the symmetric traveling salesman polytope are given. An identification procedure accepts as input the support graph of a point which does not belong to the polytope, and returns as output some of the facet inducing inequalities violated by the point. A procedure which always accomplishes this task is calledexact, otherwise it is calledheuristic. We give exact procedures for the subtour elimination and the 2-matching constraints, based on the Gomory—Hu and Padberg—Rao algorithms respectively. Efficient reduction procedures for the input graph are proposed which accelerate these two algorithms substantially. Exact and heuristic shrinking conditions for the input graph are also given that yield efficient procedures for the identification of simple and general comb inequalities and of some elementary clique tree inequalities. These procedures constitute the core of a polytopal cutting plane algorithm that we have devised and programmed to solve a substantial number of large-scale problem instances with sizes up to 2392 nodes to optimality.Partial financial support by NSF grant DMS8508955 and ONR grant R&T4116663.Work done while visiting New York University. Partial financial support by a New York University Research Challenge Fund grant and ONR grant R&T4116663.