A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints

A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.