pith. sign in

arxiv: 1907.09054 · v1 · pith:SUMWVIJZnew · submitted 2019-07-21 · 💻 cs.DS · cs.DM· math.OC

Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps

Samuel C. Gutekunst , David P. Williamson This is my paper

Pith reviewed 2026-05-24 18:08 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.OC
keywords traveling salesman problemsemidefinite programmingintegrality gapsubtour LPsimplicial instancescombinatorial optimizationrelaxation
0
0 comments X

The pith

A family of simplicial TSP instances shows that SDP relaxations have unbounded integrality gaps.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a family of simplicial traveling salesman problem instances. On these instances the optimal tour length is known exactly, yet a prominent semidefinite programming relaxation based on permutation matrices returns a value that can be arbitrarily larger. The same instances force an unbounded gap for every SDP relaxation of the TSP listed in a recent survey. The classic subtour elimination linear program, by contrast, solves every simplicial instance to optimality. The constructions therefore provide a concrete test that future SDP relaxations must pass.

Core claim

Simplicial TSP instances exist on which the integrality gap of the de Klerk-Sotirov SDP is unbounded, and these instances imply that every SDP relaxation surveyed by Sotirov also has unbounded integrality gap, while the subtour LP has gap one.

What carries the argument

Simplicial TSP instances, a specially constructed family of graphs on which SDP values diverge from the integer optimum while the subtour LP matches it.

If this is right

  • The permutation-matrix SDP of de Klerk and Sotirov has unbounded integrality gap.
  • Every SDP relaxation in Sotirov's survey has unbounded integrality gap.
  • The subtour elimination LP solves simplicial instances exactly.
  • Any new SDP relaxation of the TSP must be evaluated on these simplicial instances to check its gap.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Combining SDP relaxations with subtour inequalities might close the gap on these instances.
  • The results highlight the difficulty of capturing tour structure with semidefinite constraints alone.
  • These instances could be used to test whether adding linear cuts to SDPs improves their performance on TSP.

Load-bearing premise

The simplicial TSP instances can be constructed explicitly so that the SDP optimum, the optimal tour length, and their growing ratio are all computable.

What would settle it

Finding a sequence of simplicial TSP instances where the ratio of the SDP value to the optimal tour length stays bounded would disprove the claim of unbounded gaps.

Figures

Figures reproduced from arXiv: 1907.09054 by David P. Williamson, Samuel C. Gutekunst.

Figure 1
Figure 1. Figure 1: n−g g ai for g = 2, 5, and 10. For each curve (and any value of n), the values a1, ..., ad−1 are taken by sampling the curve at x = 1 d , 2 d , ..., d−1 d ; the value of ad is half the value at x = 1. The dotted curve shows g = 2, the dashed curve shows g = 5, and the remaining curve shows g = 10. blocks. Y = 1 2n   2In A A A B B B B B B B B A 2In A A B B B B B B B B A A 2In A B B B B … view at source ↗
read the original 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, e.g., algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [9] present an 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 \emph{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 [24]. In contrast, the subtour LP performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims to construct a family of simplicial TSP instances demonstrating that the integrality gap of the permutation-matrix SDP of de Klerk and Sotirov is unbounded, and that the same instances force unbounded gaps for every SDP relaxation surveyed in Section 2 of Sotirov [24]. It contrasts this with the subtour LP, which has zero gap on these instances, and positions the family as a litmus test for future SDP relaxations of TSP.

Significance. If the explicit construction and exact SDP computations hold, the result would be significant: it supplies a concrete, symmetry-reduced family separating a broad class of SDP relaxations from the subtour LP on TSP, with the gap tending to infinity. The approach of using simplicial instances to obtain closed-form SDP values is a methodological strength when the instances are fully specified.

major comments (2)
  1. [Abstract / main results] Abstract / main-results paragraph: the central claim requires an explicit family of simplicial TSP instances on which (i) the optimal tour length is known exactly, (ii) the SDP optimum after symmetry reduction admits an exact closed-form value independent of instance size, and (iii) the ratio tends to infinity. No such explicit instance definitions, symmetry-reduced SDP formulation, or closed-form expressions appear in the provided text, so the unbounded-gap statement cannot be verified.
  2. [Abstract / main results] Implication paragraph: the assertion that the simplicial instances force unbounded gaps for every SDP listed in Sotirov [24] is stated without the required reduction or argument showing why each surveyed SDP (not merely the de Klerk–Sotirov one) evaluates to a value whose ratio to the tour length diverges.
minor comments (1)
  1. [Introduction] Define 'simplicial TSP instance' with a formal definition and an example before the main claims, as the term is used throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [Abstract / main results] Abstract / main-results paragraph: the central claim requires an explicit family of simplicial TSP instances on which (i) the optimal tour length is known exactly, (ii) the SDP optimum after symmetry reduction admits an exact closed-form value independent of instance size, and (iii) the ratio tends to infinity. No such explicit instance definitions, symmetry-reduced SDP formulation, or closed-form expressions appear in the provided text, so the unbounded-gap statement cannot be verified.

    Authors: The explicit family of simplicial TSP instances is defined in Section 3, the symmetry-reduced SDP formulation appears in Section 4, and the closed-form SDP value together with the proof that the gap tends to infinity is given in Theorem 5.1. We will revise the abstract/main-results paragraph to add explicit forward references to these sections so that the construction and its properties are immediately locatable. revision: yes

  2. Referee: [Abstract / main results] Implication paragraph: the assertion that the simplicial instances force unbounded gaps for every SDP listed in Sotirov [24] is stated without the required reduction or argument showing why each surveyed SDP (not merely the de Klerk–Sotirov one) evaluates to a value whose ratio to the tour length diverges.

    Authors: Section 6 contains the argument that every SDP surveyed in Section 2 of Sotirov [24] evaluates to exactly the same value as the de Klerk–Sotirov SDP on simplicial instances (owing to the simplicial structure forcing all these formulations to coincide). We will revise the implication paragraph to reference Section 6 and briefly outline this reduction. revision: yes

Circularity Check

0 steps flagged

No circularity detected; results rest on explicit construction of instances

full rationale

The paper derives its claims via direct construction of a family of simplicial TSP instances, on which optimal tour length is known by definition of the instances and SDP value is obtained via symmetry reduction. No step reduces a claimed prediction to a fitted parameter, renames a known result, or relies on a load-bearing self-citation whose content is unverified. The second claim (unbounded gap for all surveyed SDPs) follows from the same explicit instances applying to the formulations in Sotirov [24], an external reference. The derivation chain is therefore self-contained and does not collapse by construction to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper relies on standard definitions of integrality gap and SDP relaxations from combinatorial optimization; the main addition is the new family of instances.

axioms (1)
  • standard math Standard definitions and properties of integrality gaps for LP and SDP relaxations of TSP.
    Invoked to define and compare the gaps of the relaxations.
invented entities (1)
  • simplicial TSP instances no independent evidence
    purpose: To serve as a family of instances on which SDP integrality gaps are unbounded while the subtour LP gap is zero.
    Newly introduced in the paper as the central technical device.

pith-pipeline@v0.9.0 · 5721 in / 1277 out tokens · 56752 ms · 2026-05-24T18:08:05.585891+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP

    cs.DM 2019-07 unverdicted novelty 6.0

    The subtour elimination constraints imply the matrix-tree theorem SDP constraint for the TSP.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · cited by 1 Pith paper

  1. [1]

    K. M. Anstreicher. Eigenvalue bounds versus semidefinite relaxations for the quadratic assign- ment problem. SIAM Journal on Optimization , 11(1):254–265, 2000

    work page 2000

  2. [2]

    Burer and D

    S. Burer and D. Vandenbussche. Solving lift-and-project relaxations of binary integer programs. SIAM Journal on Optimization , 16(3):726–750, 2006

    work page 2006

  3. [3]

    Christofides

    N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976

    work page 1976

  4. [4]

    W. H. Cunningham. On bounds for the metric TSP. Manuscript, School of Mathematics and Statistics, Carleton University, Ottawa, Canada, 1986

    work page 1986

  5. [5]

    Cvetkovi´ c, M.ˇCangalovi´ c, and V

    D. Cvetkovi´ c, M.ˇCangalovi´ c, and V. Kovaˇ cevi´ c-Vujˇ ci´ c. Semidefinite programming methods for the symmetric traveling salesman problem. In G. Cornu´ ejols, R. E. Burkard, and G. J. Woeginger, editors, Integer Programming and Combinatorial Optimization, 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, Proceedings, volume 1610 of L...

    work page 1999

  6. [6]

    Dantzig, R

    G. Dantzig, R. Fulkerson, and S. Johnson. Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America , 2(4):393–410, 1954

    work page 1954

  7. [7]

    de Klerk, F

    E. de Klerk, F. De Oliveira Filho, and D. Pasechnik. Relaxations of combinatorial problems via association schemes. In M. F. Anjos and J. B. Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization, volume 166 ofInternational Series in Operations Research & Management Science , pages 171–199. Springer, Boston, 2012

    work page 2012

  8. [8]

    de Klerk, D

    E. de Klerk, D. V. Pasechnik, and R. Sotirov. On semidefinite programming relaxations of the traveling salesman problem. SIAM Journal on Optimization , 19(4):1559–1573, 2008

    work page 2008

  9. [9]

    de Klerk and R

    E. de Klerk and R. Sotirov. Improved semidefinite programming bounds for quadratic as- signment problems with suitable symmetry. Mathematical Programming, 133(1):75–91, Jun 2012

    work page 2012

  10. [10]

    Goemans and F

    M. Goemans and F. Rendl. Combinatorial optimization. In H. Wolkowicz, R. Saigal, and L. Vandenberghe, editors, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, pages 343–360. Springer, Boston, 2000

    work page 2000

  11. [11]

    M. X. Goemans. Worst-case comparison of valid inequalities for the TSP. Mathematical Programming, 69:335–349, 1995. 31

    work page 1995

  12. [12]

    R. M. Gray. Toeplitz and circulant matrices: A review. Foundations and Trends R⃝ in Com- munications and Information Theory , 2(3):155–239, 2006

    work page 2006

  13. [13]

    S. C. Gutekunst and D. P. Williamson. The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem. SIAM Journal on Optimization , 28(3):2073– 2096, 2018

    work page 2073

  14. [14]

    S. W. Hadley, F. Rendl, and H. Wolkowicz. A new lower bound via projection for the quadratic assignment problem. Mathematics of Operations Research, 17(3):727–739, 1992

    work page 1992

  15. [15]

    Held and R

    M. Held and R. M. Karp. The traveling-salesman problem and minimum spanning trees. Operations Research, 18(6):1138–1162, 1970

    work page 1970

  16. [16]

    R. A. Horn and C. R. Johnson. Topics in Matrix Analysis . Cambridge University Press, Cambridge U.K., 1991

    work page 1991

  17. [17]

    Jeffrey and H.-H

    A. Jeffrey and H.-H. Dai. Handbook of Mathematical Formulas and Integrals. Academic Press, New York, fourth edition, 2008

    work page 2008

  18. [18]

    Karpinski, M

    M. Karpinski, M. Lampis, and R. Schmied. New inapproximability bounds for TSP. Journal of Computer and System Sciences , 81(8):1665–1677, 2015

    work page 2015

  19. [19]

    T. C. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. Econometrica: Journal of the Econometric Society , pages 53–76, 1957

    work page 1957

  20. [20]

    Lov´ asz and A

    L. Lov´ asz and A. Schrijver. Cones of matrices and set-functions and 0–1 optimization. SIAM Journal on Optimization , 1(2):166–190, 1991

    work page 1991

  21. [21]

    Povh and F

    J. Povh and F. Rendl. Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optimization, 6(3):231–241, 2009

    work page 2009

  22. [22]

    Serdyukov

    A. Serdyukov. On some extremal walks in graphs. Upravlyaemye Sistemy, 17:76–79, 1978

    work page 1978

  23. [23]

    D. B. Shmoys and D. P. Williamson. Analyzing the Held-Karp TSP bound: A monotonicity property with application. Information Processing Letters, 35(6):281–285, 1990

    work page 1990

  24. [24]

    R. Sotirov. SDP relaxations for some combinatorial optimization problems. In M. F. Anjos and J. B. Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization , pages 795–819. Springer US, Boston, MA, 2012

    work page 2012

  25. [25]

    D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms . Cambridge University Press, New York, 2011

    work page 2011

  26. [26]

    L. A. Wolsey. Heuristic analysis, linear programming and branch and bound. In V. J. Rayward- Smith, editor, Combinatorial Optimization II , pages 121–134. Springer Berlin Heidelberg, Berlin, Heidelberg, 1980

    work page 1980

  27. [27]

    Q. Zhao, S. E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite programming relaxations for the quadratic assignment problem. Journal of Combinatorial Optimization , 2(1):71–109, Mar 1998. 32 A Proofs of Trigonometric and Algebraic Identities In the appendix, we sketch pertinent results from Gutekunst and Williamson [13]. Lemma (Lemma 4.8). Letn be even a...

    work page 1998

  28. [28]

    Equivalently, a(0) =b(0) = 1

    ∑d i=1ai = ∑d i=1bi = 1. Equivalently, a(0) =b(0) = 1

    work page

  29. [29]

    b(k) =− ( 1− 2 n ) a(k)− 2 n

    work page

  30. [30]

    For k = 1,...,d, a(k) = { d−2 n−2, if k = 1 − 2 n−2, otherwise

    work page

  31. [31]

    For the first result, we use the identity d∑ j=1 cos (2πjk n ) =−1 + (−1)k 2 with k = 1

    b1≤ 4π2 n3 Proof. For the first result, we use the identity d∑ j=1 cos (2πjk n ) =−1 + (−1)k 2 with k = 1. Then d∑ i=1 ai = 2 n− 2 d∑ i=1 ( cos (πi d ) + 1 ) = 2 n− 2 (−1 +d) = 1. 33 Similarly d∑ i=1 bi = d−1∑ i=1 (4 n− ( 1− 2 n ) ai ) + (2 n− ( 1− 2 n ) ai ) = (d− 1) 4 n + 2 n− ( 1− 2 n ) d∑ i=1 ai = 1. For the second result, b(k) = d∑ i=1 cos (2πik n ) b...

    work page