The asymmetric travelling salesman problem and a reformulation of Miller–Tucker–Zemlin constraints

In this paper we compare the linear programming (LP) relaxations of several old and new formulations for the asymmetric travelling salesman problem (ATSP). The main result of this paper is the derivation of a compact formulation whose LP relaxation is characterized by a set of circuit inequalities given by Grotschel and Padberg. The new compact model is an improved and disaggregated version of a well-known model for the ATSP based on the subtour elimination constraints. The circuit inequalities are weaker than the subtour elimination constraints given by Dantzig et al. However, each one of these circuit inequalities can be lifted into several different facet defining inequalities which are not dominated by the subtour elimination inequalities. We show that some of the inequalities involved in the previously mentioned compact formulation can be lifted in such a way that, by projection, we obtain a small subset of the so-called Dk ^<– and Dk^–> inequalities. This shows that the LP relaxation of our strongest model is not dominated by the LP relaxation of the model presented by Dantzig et al. The new models motivate a new classification of formulations for the ATSP.