The graphical asymmetric traveling salesman polyhedron: Symmetric inequalities

A present trend in the study of the symmetric traveling salesman polytope is to use, as a relaxation of the polytope, the graphical traveling salesman polyhedron (GTSP). Following a parallel approach for the asymmetric traveling salesman polytope, we define the graphical asymmetric traveling salesman problem on a general digraph D and its associated polyhedron GATSP(D). We give basic polyhedral results and lifting theorems for GATSP(D) and we give a general condition for a facet-defining inequality for GTSP to yield a symmetric facet-defining inequality for GATSP. Using this approach we show that all known major families of facet-defining inequalities of GTSP define facets of GATSP. Finally, we discuss possible extension of these results to the asymmetric traveling salesman polytope.