| Article ID: | iaor20002461 |
| Country: | Serbia |
| Volume: | 9 |
| Issue: | 2 |
| Start Page Number: | 157 |
| End Page Number: | 168 |
| Publication Date: | Jul 1999 |
| Journal: | Yugoslav Journal of Operations Research |
| Authors: | Cvetkovi Drago, Kovaevi-Vuji Vera, angalovi Mirjana |
| Keywords: | networks: path |
We apply semidefinite programming to the symmetric traveling salesman problem. The TSP is modeled as a problem of discrete semidefinite programming. In order to estimate the optimal objective value, a class of semidefinite relaxations of the TSP model is defined. Experimental results with randomly generated examples show that the proposed relaxation gives considerably better bounds than 2-matching and 1-tree relaxations.