FACETS OF THE ASYMMETRIC TRAVELING SALESMAN POLYTOPE

被引:36
作者
FISCHETTI, M
机构
关键词
TRAVELING SALESMAN PROBLEMS; POLYTOPES;
D O I
10.1287/moor.16.1.42
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper we consider the Asymmetric Traveling Salesman polytope, P(n), defined as the convex hull of the incidence vectors of tours in a complete digraph with n vertices, and its monotonization, Papproximately(N). Several classes of valid inequalities for both these polytopes have been introduced in the literature which are not known to define facets of P(n) or Papproximately(n). We describe a general technique which can often be used to prove that a given inequality defines a facet of P(n). The method is applied to prove that the so-called D(k)+, D(k)-, C3, comb and C2 inequalities define facets of P(n), thus solving open problems. As for the monotone polytope, a necessary and sufficient condition for a facet-defining inequality of P(n) to define a facet of Papproximately(n) as well, is introduced which applies to the D(k)+, D(k)-, C3, comb and C2 inequalities. In addition, a simple procedure for transforming any facet-defining inequality of P(n) into an equivalent one which also defines a facet of Papproximately(n), is given.
引用
收藏
页码:42 / 56
页数:15
相关论文
共 14 条
  • [1] BALAS E, 1988, MSRR551 GSIA CARN U
  • [2] BALAS E, 1989, SIAM J DISCRETE MATH, V3, P425
  • [3] Chvatal V., 1973, Mathematical Programming, V5, P29, DOI 10.1007/BF01580109
  • [4] FISCHETTI M, 1988, OR883 DEIS U BOL TEC
  • [5] FISCHETTI M, 1988, OR881 DEIS U BOL TEC
  • [6] Grotschel M., 1977, Zeitschrift fur Operations Research, Serie A (Theorie), V21, P33, DOI 10.1007/BF01918456
  • [7] CLIQUE TREE INEQUALITIES AND THE SYMMETRICAL TRAVELING SALESMAN PROBLEM
    GROTSCHEL, M
    PULLEYBLANK, WR
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 1986, 11 (04) : 537 - 569
  • [8] SYMMETRIC TRAVELING SALESMAN PROBLEM .2. LIFTING THEOREMS AND FACETS
    GROTSCHEL, M
    PADBERG, MW
    [J]. MATHEMATICAL PROGRAMMING, 1979, 16 (03) : 281 - 302
  • [9] SYMMETRIC TRAVELING SALESMAN PROBLEM .1. INEQUALITIES
    GROTSCHEL, M
    PADBERG, MW
    [J]. MATHEMATICAL PROGRAMMING, 1979, 16 (03) : 265 - 280
  • [10] Grotschel M., 1985, TRAVELING SALESMAN P