On tightening the relaxations of Miller-Tucker-Zemlin formulations for asymmetric traveling salesman problems
成果类型：
Article
署名作者：
Sherali, HD; Driscoll, PJ
署名单位：
Virginia Polytechnic Institute & State University; United States Department of Defense; United States Army; United States Military Academy
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.50.4.656.2865
发表日期：
2002
页码：
656-669
关键词：
摘要：
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 (199 1) 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.