Article ID: | iaor19921180 |
Country: | Netherlands |
Volume: | 49 |
Issue: | 2 |
Start Page Number: | 163 |
End Page Number: | 187 |
Publication Date: | Dec 1990 |
Journal: | Mathematical Programming |
Authors: | Pulleyblank W.R., Boyd S.C. |
A commonly studied relaxation of the travelling salesman problem is obtained by adding subtour elimination constraints to the constraints of a 2-factor problem and removing the integrality requirement. The authors investigate the problem of solving this relaxation for a special type of objective function. They also discuss some ways in which this relates to the concept of rank introduced by Chvátal.