Article ID: | iaor2007459 |
Country: | Netherlands |
Volume: | 3 |
Issue: | 1 |
Start Page Number: | 20 |
End Page Number: | 32 |
Publication Date: | Mar 2006 |
Journal: | Discrete Optimization |
Authors: | Sarin Subhash C., Sherali Hanif D., Tsai Pei-Fang |
In this paper, we present a new class of polynomial length formulations for the asymmetric traveling salesman problem (ATSP) by lifting an ordered path-based model using logical restrictions in concert with the Reformulation–Linearization Technique (RLT). We show that a relaxed version of this formulation is equivalent to a flow-based ATSP model, which in turn is tighter than the formulation based on the exponential number of Dantzig–Fulkerson–Johnson (DFJ) subtour elimination constraints. The proposed lifting idea is applied to derive a variety of new formulations for the ATSP, and we explore several dominance relationships among these. We also extend these formulations to include precedence constraints in order to enforce a partial order on the sequence of cities to be visited in a tour. Computational results are presented to exhibit the relative tightness of our formulations and the efficacy of the proposed lifting process.