SYMMETRIC TRAVELING SALESMAN PROBLEM .1. INEQUALITIES

被引:125
作者
GROTSCHEL, M [1 ]
PADBERG, MW [1 ]
机构
[1] NYU,NEW YORK,NY 10003
关键词
Convex Polytopes; Facets; Linear Inequalities; Travelling Salesman Problem;
D O I
10.1007/BF01582116
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We investigate several classes of inequalities for the symmetric travelling salesman problem with respect to their facet-defining properties for the associated polytope. A new class of inequalities called comb inequalities is derived and their number shown to grow much faster with the number of cities than the exponentially growing number of subtour-elimination constraints. The dimension of the travelling salesman polytope is calculated and several inequalities are shown to define facets of the polytope. In part II (On the travelling salesman problem II: Lifting theorems and facets") we prove that all subtour-elimination and all comb inequalities define facets of the symmetric travelling salesman polytope. © 1979 The Mathematical Programming Society."
引用
收藏
页码:265 / 280
页数:16
相关论文
共 29 条
  • [21] Karp R.M., 1972, COMPLEXITY COMPUTER, P83
  • [22] Kuhn H., 1955, B AM MATH SOC, V61, P557
  • [23] MAURRAS JF, 1976, THESIS U PARIS
  • [24] MENGER K, 1932, ERG MATH K 2 TEUBN L, P11
  • [25] NETTO E, LEHRBUCH COMBINATORI
  • [26] NORMAN RZ, 1955, B AM MATH SOC, V61, P559
  • [27] Padberg M.W., 1974, MATH PROGRAM, V7, P32
  • [28] PADBERG MW, 1977, TJ WATSON RES REPORT
  • [29] Stoer J., 1970, CONVEXITY OPTIMIZATI