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, P̃ n . Several classes of valid inequalities for both there polytopes have been introduced in the literature which are not known to define facets of P n or P̃ 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 P̃ 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 P̃ n , is given.