Semidefinite relaxations of the traveling salesman problem. (English) Zbl 1006.90065

The authors apply semidefinite programming to the symmetric Traveling Salesman Problem (TSP). The crucial idea is to model the TSP as a discrete semidefinite programming problem in which, generally the exponential set of constraints arising from the Hamiltonian cycles, is compressed into the smaller one (polynomial in size). For this aim the algebraic connectivity of graphs, i.e., the second smallest eigenvalue of the Laplacian spectrum of a graph, is used. When estimating the optimal value, a class of semidefinite relaxations of the TSP model is defined. The experimental results with randomly generated graphs (up to 20 vertices), when compared with standard relaxations such as 2-matching and 1-tree relaxations, show that the proposed relaxation gives considerably better bounds.


90C27 Combinatorial optimization
90C22 Semidefinite programming