A new relaxation framework for quadratic assignment problems based on matrix splitting

DOI10.1007/s12532-010-0012-6zbMath1191.65071OpenAlexW2019352048MaRDI QIDQ977330

Jiming Peng, Xiaoxue Li, Hans D. Mittelmann

Publication date: 21 June 2010

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-010-0012-6

zbMATH Keywords

semidefinite programmingnumerical examplesrelaxationquadratic assignment problemlower boundmatrix splitting

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Quadratic programming (90C20) Discrete location and assignment (90B80)

Related Items

A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives, Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers, A new exact discrete linear reformulation of the quadratic assignment problem, On New Classes of Nonnegative Symmetric Tensors, A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique, Semidefinite programming approach for the quadratic assignment problem with a sparse graph, Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting, On solving a hard quadratic 3-dimensional assignment problem, A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases

Uses Software

• Matlab
• QAPLIB
• SDPT3
• CVX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• A survey for the quadratic assignment problem
• Bounds for the quadratic assignment problem using the bundle method
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• Solving large quadratic assignment problems on computational grids
• Minimax nonredundant channel coding
• Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
• The Quadratic Assignment Problem
• Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices Based on Semidefinite Programming
• Assignment Problems and the Location of Economic Activities
• Bounds on the Performance of Vector-Quantizers Under Channel Errors
• Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• Comparison of iterative searches for the quadratic assignment problem
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• A new bound for the quadratic assignment problem based on convex quadratic programming