Abstract:
Arthanari (On the traveling salesman problem, presented at the XI Symposium on Mathematical Programming held at Bonn, West Germany, 1982) proposed a Multistage-insertion (MI)-formulation of the symmetric traveling salesman problem (STSP). This formulation has a polynomial number of constraints. Carr (Polynomial separation procedures and facet determination for inequalities of the traveling salesman polytope, Ph.D. Thesis, Carneige Mellon University, 1995; Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time, preprint, 1996) 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.