Optimizing over the subtour polytope of the travelling salesman problem (Q803048)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Optimizing over the subtour polytope of the travelling salesman problem |
scientific article |
Statements
Optimizing over the subtour polytope of the travelling salesman problem (English)
0 references
1990
0 references
The paper is concerned with polyhedral aspects of the symmetric travelling salesman problem. In particular functions related to clique trees [see \textit{M. Grötschel} and \textit{W. Pulleyblank}, Math. Oper. Res. 11, 537-569 (1986; Zbl 0626.90060)] are optimized over the subtour polytope S given by the 2-factor and subtour elimination constraints. Further the Chvátal rank of clique tree inequalities is studied. Finally, the structure of the vertices of the polytope S is investigated.
0 references
polyhedral aspects
0 references
symmetric travelling salesman
0 references
clique trees
0 references
subtour polytope
0 references
Chvátal rank
0 references
