On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems

Hanif D. Sherali and Patrick J. Driscoll ()
Additional contact information
Hanif D. Sherali: Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Patrick J. Driscoll: Department of Systems Engineering, U.S. Military Academy, West Point, New York 10996

Operations Research, 2002, vol. 50, issue 4, 656-669

Abstract: 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 (1991) 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.

Keywords: Programming; integers: Reformulation-linearization technique; asymmetric traveling salesman problem; Miller-Tucker-Zemlin; tight relaxations; precedence constrained asymmetric traveling salesman problem (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.4.656.2865 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:50:y:2002:i:4:p:656-669

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().