FACETS OF THE ASYMMETRIC TRAVELING SALESMAN POLYTOPE

In this paper we consider the Asymmetric Traveling Salesman polytope, P(n), defined as the convex hull of the incidence vectors of tours in a complete digraph with n vertices, and its monotonization, Papproximately(N). Several classes of valid inequalities for both these polytopes have been introduced in the literature which are not known to define facets of P(n) or Papproximately(n). We describe a general technique which can often be used to prove that a given inequality defines a facet of P(n). The method is applied to prove that the so-called D(k)+, D(k)-, C3, comb and C2 inequalities define facets of P(n), thus solving open problems. As for the monotone polytope, a necessary and sufficient condition for a facet-defining inequality of P(n) to define a facet of Papproximately(n) as well, is introduced which applies to the D(k)+, D(k)-, C3, comb and C2 inequalities. In addition, a simple procedure for transforming any facet-defining inequality of P(n) into an equivalent one which also defines a facet of Papproximately(n), is given.