Optimizing over the subtour polytope of the travelling salesman problem (Q803048)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Optimizing over the subtour polytope of the travelling salesman problem |
scientific article; zbMATH DE number 4199993
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Optimizing over the subtour polytope of the travelling salesman problem |
scientific article; zbMATH DE number 4199993 |
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
0.7804819345474243
0 references
0.7784262299537659
0 references
0.7715840339660645
0 references
