On Semidefinite Programming Relaxations of the Traveling Salesman Problem

DOI10.1137/070711141zbMath1196.90094arXiv0902.1843OpenAlexW2125297716WikidataQ56874368 ScholiaQ56874368MaRDI QIDQ3648520

Renata Sotirov, Etienne de Klerk, Dimitrii V. Pasechnik

Publication date: 27 November 2009

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0902.1843

zbMATH Keywords

semidefinite programmingcombinational optimization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items (25)

An Improved Interior-Point Cutting-Plane Method for Binary Quadratic Optimization ⋮ On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems ⋮ On semidefinite programming bounds for graph bandwidth ⋮ A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives ⋮ Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ A primal barrier function phase I algorithm for nonsymmetric conic optimization problems ⋮ Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP ⋮ Minimum energy configurations on a toric lattice as a quadratic assignment problem ⋮ A semidefinite optimization approach to the target visitation problem ⋮ On Integrality in Semidefinite Programming for Discrete Optimization ⋮ Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry ⋮ The symmetric quadratic traveling salesman problem ⋮ A comparison of lower bounds for the symmetric circulant traveling salesman problem ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ A polynomial time constraint-reduced algorithm for semidefinite optimization problems ⋮ The demand weighted vehicle routing problem ⋮ Gaddum's test for symmetric cones ⋮ New semidefinite programming relaxations for the linear ordering and the traveling salesman problem ⋮ Relaxations of Combinatorial Problems Via Association Schemes ⋮ Invariant Semidefinite Programs ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ Exploiting special structure in semidefinite programming: a survey of theory and applications ⋮ Exploiting symmetry in copositive programs via semidefinite hierarchies

This page was built for publication: On Semidefinite Programming Relaxations of the Traveling Salesman Problem