On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem

Arthanari proposed a Multistage-insertion (MI)-formulation of the symmetric traveling salesman problem (STSP). This formulation has a polynomial number of constraints. Carr proposed the Cycle-shrink relaxation of the STSP. In this paper, we show that there exists a natural transformation which establishes a one-to-one correspondence between the variables of the two formulations, say X and U, such that X is feasible for MI-formulation if and only if U is feasible for the other. The size of the Cycle-shrink formulation is larger than that of the MI-formulation, both in the number of variables and constraints. However, both are compact descriptions of the subtour elimination polytope.