Optimization Online


On semidefinite programming relaxations of the traveling salesman problem

Etienne De Klerk (e.deklerk***at***uvt.nl)
Dmitrii V. Pasechnik (dima***at***ntu.edu.sg)
Renata Sotirov (R.Sotirov***at***uvt.nl)

Abstract: We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in the paper: [D. Cvetkovic, M. Cangalovic and V. Kovacevic-Vucic. Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem. In Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, 1999, 126--136, Springer-Verlag, London, UK.] Unlike the relaxation of Cvetkovic et al., the new SDP relaxation is not dominated by the linear programming relaxation with sub-tour elimination constraints.

Keywords: semidefinite programming, traveling salesman problem

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization

Citation: SIAM Journal on Optimization, 19(4), 1559-1573, 2008. Note: Figure 5.1 is a corrected version of the incorrect figure that appeared in print.

Download: [PDF]

Entry Submitted: 12/17/2007
Entry Accepted: 12/17/2007
Entry Last Modified: 02/08/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society