Symmetric inequalities and their composition for asymmetric travelling salesman polytopes

The Asymmetric Travelling Salesman (ATS) polytope ATSP(V) is the convex hull of incidence vectors of all Hamiltonian circuits in a complete digraph with node set V. This paper studies classes of valid symmetric inequalities at less than or equal to a(0) for ATS polytopes with coefficients satisfying a(ij)=a(ji) for all pairs of cities i and j. Of particular interest are those inequalities derived from facet-defining inequalities for Symmetric Travelling Salesman Polytopes (STSPs). We show that known classes of STSP facet-defining inequalities, such as Path, Wheelbarrow, Chain, and Ladder inequalities, induce symmetric ATSP facet-defining inequalities. For ATSP(V) with |V|≥8, we show that there are precisely four types of STSP facet-defining inequalities that do not induce ATSP facets. We propose a Tree Composition of symmetric inequalities and use it to generate a large new class of symmetric facet-defining inequalities for ATS polytopes, subsuming all nonspanning Clique Tree inequalities. A Hamiltonian path approach is used for most of the polyhedral proofs in the paper.