Paper Info
Title
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
Abstract
The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Programming 133(1):75-91.] present a semidefinite program (SDP) based on permutation matrices and symmetry reduction; they show that it is incomparable to the subtour elimination linear program but generally dominates it on small instances. We provide a family of simplicial TSP instances that shows that the integrality gap of this SDP is unbounded. Second, we show that these simplicial TSP instances imply the unbounded integrality gap of every SDP relaxation of the TSP mentioned in the survey on SDP relaxations of the TSP in section 2 of Sotirov [Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds., Handbook on Semi-definite, Conic and Polynomial Optimization (Springer, New York), 795-819.]. In contrast, the subtour linear program performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP.
Year
DOI
Venue
2022
10.1287/moor.2020.1100
MATHEMATICS OF OPERATIONS RESEARCH
Keywords
DocType
Volume
traveling salesman problem, integrality gap, semidefinite programming
Journal
47
Issue
ISSN
Citations 
1
0364-765X
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Gutekunst Samuel C.100.34
David P. Williamson23564413.34