ADMM for the SDP relaxation of the QAP

DOI10.1007/s12532-018-0148-3zbMath1411.90258arXiv1512.05448OpenAlexW2963961556WikidataQ129248478 ScholiaQ129248478MaRDI QIDQ1741118

Danilo Elias Oliveira, Henry Wolkowicz, Yang-yang Xu

Publication date: 3 May 2019

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

Full work available at URL: https://arxiv.org/abs/1512.05448

zbMATH Keywords

quadratic assignment problemalternating direction method of multiplierslarge scalesemidefinite programming relaxationfacial reductiondoubly nonnegative

Mathematics Subject Classification ID

Semidefinite programming (90C22) Large-scale problems in mathematical programming (90C06) Optimality conditions and duality in mathematical programming (90C46) Discrete location and assignment (90B80) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Mathematical Programming Models and Exact Algorithms, SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning, Lower bounds for the bandwidth problem, A strengthened Barvinok-Pataki bound on SDP rank, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP, Partitioning through projections: strong SDP bounds for large graph partition problems, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Semidefinite programming approach for the quadratic assignment problem with a sparse graph, Max-norm optimization for robust matrix recovery, A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem, Algorithm 996, On Solving the Quadratic Shortest Path Problem, ADMM_QAP

Uses Software

• EIGIFP
• QAPLIB
• SDPT3
• SDPNAL+
• BBCPOP

Cites Work

• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• Alternating direction augmented Lagrangian methods for semidefinite programming
• QAPLIB-A quadratic assignment problem library
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• Bounds for the quadratic assignment problem using the bundle method
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• Recent advances in the solution of quadratic assignment problems
• Local minima and convergence in low-rank semidefinite programming
• The Quadratic Assignment Problem
• $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Assignment Problems and the Location of Economic Activities
• A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• An Inverse Free Preconditioned Krylov Subspace Method for Symmetric Generalized Eigenvalue Problems
• Algorithm 996
• A Parallel Approximation Algorithm for Positive Semidefinite Programming
• A new bound for the quadratic assignment problem based on convex quadratic programming
• Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem