Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices Based on Semidefinite Programming

DOI10.1137/090748834zbMath1211.90162OpenAlexW2028920274MaRDI QIDQ3083337

Hans D. Mittelmann, Jiming Peng

Publication date: 21 March 2011

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

Full work available at URL: https://doi.org/10.1137/090748834

zbMATH Keywords

semidefinite programmingsingular value decompositionrelaxationquadratic assignment problemlower bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items

A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives, A Branch-and-Bound Algorithm for Team Formation on Social Networks, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, A new relaxation framework for quadratic assignment problems based on matrix splitting, Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting, On solving a hard quadratic 3-dimensional assignment problem, A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices

Uses Software

• QAPLIB
• SDPT3
• CVX