Estimating bounds for quadratic assignment problems associated with Hamming and Manhattan distance matrices based on semidefinite programming

DOI10.1137/090748834MaRDI QIDQ3083337zbMATH OpenOpenAlexFDO

Authors 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

singular value decompositionquadratic assignment problemsemidefinite programminglower boundrelaxation

Mathematics Subject Classification ID

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

Recommendations

• A low-dimensional semidefinite relaxation for the quadratic assignment problem
• scientific article; zbMATH DE number 1894380
• A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives
• Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
• A New Matrix Splitting Based Relaxation for the Quadratic Assignment Problem

Cited in

(11)

• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
• On solving a hard quadratic 3-dimensional assignment problem
• Combinatorial optimization problems in engineering applications
• A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices
• Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting
• Semidefinite approximations for quadratic programs over orthogonal matrices
• 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
• A new relaxation framework for quadratic assignment problems based on matrix splitting
• Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
• Characteristics of the Distribution of Hamming Distance Values Between Multidimensional Assignment Problem Solutions

Describes a project that uses

Uses Software

• QAPLIB
• SDPT3
• CVX

This page was built for publication: Estimating bounds for quadratic assignment problems associated with Hamming and Manhattan distance matrices based on semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3083337)