Semidefinite Relaxations of The Traveling Salesman Problem


Dragoš Cvetković, Mirjana Čangalović, Vera Kovačević-Vujčić




We apply semidefinite programming to the symmetric traveIing salesman problem (TSP). 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 relaxation.