A transformation technique is proposed that permits one to derive the linear description of the image X of a polyhedron Z under an affine linear transformation from the (given) linear description of Z. This result is used to analytically compare various formulation of the asymmetric travelling salesman problem to the standard formulation due to Dantzig, Fulkerson and Johnson which are all shown to be ‘weaker formulations’ in a precise setting. The authors also apply this transformation technique to ‘symmetrize’ formulations and show, in particular, that the symmetrization of the standard asymmetric formulation results into the standard one for the symmetric version of the travelling salesman problem.
