A New Formulation for the Travelling Salesman Problem

The standard formulation of the travelling salesman problem on n nodes as an integer program involves use of 2ⁿ subtour elimination constraints. In this paper we provide a set of on the order of n³ constraints that define the same polytope. This is accomplished through introduction of additional variables. An additional set of $n ( n - 1 ) /2$ constraints is introduced and results in a polytope that is smaller than the subtour elimination polytope. The introduction of further variables as well as constraints results in an even smaller polytope.