On symmetric subtour problems

Recently several practical variants of the classical traveling salesman problem are proposed. These variants include the traveling purchaser problem, the prize collecting traveling salesman problem, the orienteering problem, the median shortest path problem, and the covering salesman problem. The most important common characteristic of these problems is that the salesman travels the subset of customers, i.e., the tour does not necessarily visit all nodes as in the traveling salesman problem. This class of problem is called the subtour problem. In this paper, the authors derive several valid inequalties and show some of them are facets of the polytope of the subtour problem. Further they present several integer or mixed integer programming formulations of the subtour problem and compare these formulations in terms of bounds obtained by linear programming relaxations.