SYMMETRIC TRAVELING SALESMAN PROBLEM .1. INEQUALITIES

被引：125

作者：

GROTSCHEL, M ^{[1
]}

PADBERG, MW ^{[1
]}

机构：

[1] NYU,NEW YORK,NY 10003

来源：

MATHEMATICAL PROGRAMMING | 1979年 / 16卷 / 03期

关键词：

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