Network flow precedence based formulations for the asymmetric traveling salesman problem with precedence constraints

Given a directed graph G = (V, A), a cost function c associated with the arcs of A, and a set of precedence constraints B ⊂ V × V , the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP) seeks for a minimum cost Hamiltonian circuit, starting at node 1, and such that for each (i, j) ∈ B, the node i is visited before node j. There are many ways of modelling the ATSP and several for the PCATSP. In this talk we present new formulations for the two problems that can be viewed as resulting from combining precedence variable based formulations, with network flow based formulations. As suggested in [1], the former class of formulations permits to integrate linear ordering constraints. The motivating formulation for this work is a complicated and " ugly " formulation that results from the separation of generalized subtour elimination constraints presented in [2] (see also [1]). This so called " ugly " formulation exhibits, however, one interesting feature, namely the " disjoint subpaths " property that is further explored to create more complicated formulations that combine two (or three) " disjoint path " network flow based formulations and have a stronger linear programming bound. Some of these stronger formulations are related to the ones presented for the PCATSP in [3] and can be viewed as generalizations in the space of the precedence based variables. Several sets of projected inequalities in the space of the arc and precedence variables and in the spirit of many presented in [1] are obtained by projection from these network flow based formulations. Computational results will be given for the ATSP and PCATSP to evaluate the quality of the new models and inequalities. References [1] L. Gouveia and P. Pesneau. On extended formulations for the precedence constrainted asymmetric traveling salesman problem. Networks, 48(2):77–89, 2006. [2] L. Gouveia and J. M. Pires. The asymmetric travelling salesman problem: On generalizations of disaggregated Miller-Tucker-Zemlin constraints. Discrete Applied Mathematics, 112:129–145, 2001. [3] A. N. Letchford and J.-J. Salazar-Gonzalez. Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem.