On tightening the relaxations of Miller–Tucker–Zemlin formulations for asymmetric traveling salesman problems

This paper is concerned with applying the Reformulation-Linearization Technique (RLT) to derive tighter relaxations for the Asymmetric Traveling Salesman Problem (ATSP) formulation that is based on the Miller–Tucker–Zemlin (MTZ) subtour elimination constraints. The MTZ constraints yield a compact representation for the Traveling Salesman Problem (TSP), and their use is particularly attractive in various routing and scheduling contexts that have an embedded ATSP structure. However, it is well recognized that these constraints yield weak relaxations, and with this motivation, Desrochers and Laporte have lifted the MTZ constraints into facets of the underlying ATSP polytope. We show that a novel application of the RLT process from a nonstandard MTZ representation of the ATSP reveals a new formulation of this problem that is compact, and yet theoretically as well as computationally dominates the lifted-MTZ formulation of Desrochers and Laporte. This approach is also extended to derive tight formulations for the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP), based on the MTZ subtour elimination constraints. Additional classes of valid inequalities are also developed for both these versions of the ATSP, and further ideas for developing tighter representations are suggested for future investigations.