On the symmetric travelling salesman problem I: inequalities

M Grötschel, MW Padberg - Mathematical Programming, 1979 - Springer
M Grötschel, MW Padberg
Mathematical Programming, 1979Springer
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 …
Abstract
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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果