Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

DOI10.1007/s10107-010-0411-5zbMath1270.90045OpenAlexW2109156232MaRDI QIDQ431008

Renata Sotirov, Etienne de Klerk

Publication date: 26 June 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0411-5

zbMATH Keywords

semidefinite programmingbranch and boundquadratic assignment problemgroup symmetry

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational methods for problems pertaining to mechanics of particles and systems (70-08)

Related Items

Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, On semidefinite programming bounds for graph bandwidth, Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software, 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, On semidefinite programming relaxations of maximum \(k\)-section, Lower bounds for the bandwidth problem, 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, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, Quadratic Combinatorial Optimization Using Separable Underestimators, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Relaxations of Combinatorial Problems Via Association Schemes, SDP Relaxations for Some Combinatorial Optimization Problems, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, Semidefinite programming and eigenvalue bounds for the graph partition problem

Uses Software

• QAPLIB
• SeDuMi
• YALMIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• A complete description of the traveling salesman polytope on 8 nodes
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• Recent advances in the solution of quadratic assignment problems
• Symmetry groups, semidefinite programs, and sums of squares
• Minimax nonredundant channel coding
• Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices Based on Semidefinite Programming
• Bounds on the Performance of Vector-Quantizers Under Channel Errors
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
• Optimal Assignments of Numbers to Vertices
• The Traveling-Salesman Problem and Minimum Spanning Trees