Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting

DOI10.1007/S10589-014-9663-YzbMath1338.90295OpenAlexW2017309246MaRDI QIDQ2515070

Hezhi Luo, Tao Zhu, Kim-Chuan Toh, Jiming Peng

Publication date: 10 February 2015

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-014-9663-y

zbMATH Keywords

quadratic assignment problemsemi-definite programminglower boundmatrix splittingsemi-definite relaxation

Mathematics Subject Classification ID

Semidefinite programming (90C22) Discrete location and assignment (90B80)

Related Items (7)

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation ⋮ A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives ⋮ An effective global algorithm for worst-case linear optimization under polyhedral uncertainty ⋮ Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters ⋮ Semidefinite programming approach for the quadratic assignment problem with a sparse graph ⋮ An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation ⋮ Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties

Uses Software

• Unnamed Item
• SDPT3
• CVX

Cites Work

• Unnamed Item
• Unnamed Item
• QAPLIB-A quadratic assignment problem library
• 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
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• A new relaxation framework for quadratic assignment problems based on matrix splitting
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• Generalized median graphs and applications
• Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
• The Quadratic Assignment Problem
• A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices Based on Semidefinite Programming
• A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem
• Assignment Problems and the Location of Economic Activities
• Assignment Problems
• Bounds on the Performance of Vector-Quantizers Under Channel Errors
• Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
• Matrix Analysis
• A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• An inequality for the trace of the product of two symmetric matrices
• Comparison of iterative searches for the quadratic assignment problem
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• 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

This page was built for publication: Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting