The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints

In this paper we show that a multicommodity flow (MCF) model can be aggrega ted into a node-oriented model which in turn, can be seen as a disaggregati on of the well-known Miller-Tucker-Zemlin model. Several outcomes of this n ode-oriented aggregation are also discussed: (i) the derivation of an "augm ented" MCF model with a tighter linear programming (LP) relaxation and whic h is obtained by adding to MCF a disaggregated version of the Desrochers an d Laporte inequalities together with a suitable set of linking constraints and (ii) the derivation of generalizations of the disaggregated Miller-Tuck er-Zemlin constraints for paths. These generalized constraints can then be used to show that the LP relaxation of the new and tighter MCF model implie s an exponentially sized set of lifted circuit inequalities (simple FD ineq ualities) which are known to be facet defining for the asymmetric travellin g salesman polytope, Generalizations of the disaggregated Desrochers and La porte inequalities which tighten the LP relaxation of the augmented MCF mod el are also proposed. (C) 2001 Elsevier Science B.V. All rights reserved.