Classification of travelling salesman problem formulations (Q911990)

This paper compares various Traveling Salesman Problem formulations. With respect to the bounds given by the linear programming relaxations, it is known that the classical formulation of \textit{G. B. Dantzig} et al. [Oper. Res. 2, 393-410 (1954)] is equivalent to the 2(n-1)-commodity flow formulation of \textit{R. T. Wong} [Proc. IEEE Int. Conf. Circ. Comp., 149- 152 (1980)]. The authors show that this is also true for various recent 2(n-1) and (n-1)-commodity flow formulations based on Wong's formulation, and that these formulations are superior to the 1-commodity flow formulation of \textit{B. Gavish} and \textit{S. C. Graves} [Working paper GR- 078-78, ORC, MIT (1978)] and the 2-commodity flow formulation of \textit{G. Finke, A. Claus} and \textit{E. Gunn} [Congr. Numer. 41, 167-178 (1984; Zbl 0697.90056)]. Some remarks are also provided on the relative values of the formulations with respect to the number of variables and constraints.