Relaxation of the polytope of the asymmetric traveling salesman problem on the basis of the cone of generalized Supnick's matrices

For the asymmetric traveling salesman problem, we describe a relaxation polytope that is based on the cone of generalized Supnick matrices and belongs to the space of minimal dimension. The description of the relaxation polytope is obtained by means of the earlier proposed general method [6] to construct relaxations for the permutation polytopes generated by subgroups of the symmetric group. The number of inequalities in the description is of factorial order of the size of the problem.