Semidefinite relaxations of traveling salesman problem

D. Cvetkovic, M. Cangalovic, V. Kovacevic-Vujcic

In this paper we present a discrete semidefinite programming model of the symmetric traveling salesman problem and its relaxation which is a linear SDP problem. The model and its semidefinite relaxation are based on the notion of Laplacians of graphs and on a suitable characterization of algebraic connectivity of graphs. Namely, we prove that a subgraph H of a graph G is connected if and only if certain linear transformation of the Laplacian L(H) is positive semidefinite. The relaxation proposed in this paper is substantially different from the existing relaxations. Preliminary experimental results with randomly generated examples show that it gives considerably better bounds than 2-matching and 1-tree.

Technical Report 902-98, Laboratory for Operations Research, Faculty of Organizational Sciences, University of Belgrade, November 1998