Copositive and semidefinite relaxations of the quadratic assignment problem
From MaRDI portal
Publication:834180
DOI10.1016/j.disopt.2009.01.002zbMath1167.90597OpenAlexW1987255230MaRDI QIDQ834180
Publication date: 19 August 2009
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2009.01.002
copositive programmingquadratic assignment problemsemidefinite relaxationslift-and-project relaxations
Semidefinite programming (90C22) Integer programming (90C10) Quadratic programming (90C20) Combinatorial optimization (90C27)
Related Items
Matrix Relaxations in Combinatorial Optimization, Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, The QAP-polytope and the graph isomorphism problem, On semidefinite programming bounds for graph bandwidth, Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software, Copositive programming motivated bounds on the stability and the chromatic numbers, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, A survey for the quadratic assignment problem, A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives, LP-based tractable subcones of the semidefinite plus nonnegative cone, New heuristics for the vertex coloring problem based on semidefinite programming, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, A Branch-and-Bound Algorithm for Team Formation on Social Networks, Moment approximations for set-semidefinite polynomials, On semidefinite programming relaxations of maximum \(k\)-section, Semidefinite approximations for quadratic programs over orthogonal matrices, A note on set-semidefinite relaxations of nonconvex quadratic programs, A primal barrier function phase I algorithm for nonsymmetric conic optimization problems, Minimum energy configurations on a toric lattice as a quadratic assignment problem, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, A new approximation hierarchy for polynomial conic optimization, A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Approximation hierarchies for copositive cone over symmetric cone and their comparison, A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems, Copositive optimization -- recent developments and applications, Exact SDP relaxations for quadratic programs with bipartite graph structures, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, BiqBin: Moving Boundaries for NP-hard Problems by HPC, Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization, Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems, Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, Sign patterns of inverse doubly-nonnegative matrices, ADMM for the SDP relaxation of the QAP, QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming, SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Contribution of copositive formulations to the graph partitioning problem, Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems, Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems, Measuring instance difficulty for combinatorial optimization problems, Quadratic factorization heuristics for copositive programming, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation, A proximal DC approach for quadratic assignment problem, Relaxations of Combinatorial Problems Via Association Schemes, Copositive Programming, SDP Relaxations for Some Combinatorial Optimization Problems, An evaluation of semidefinite programming based approaches for discrete lot-sizing problems, An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming, Algorithm 996, SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0), Depth-first simplicial partition for copositivity detection, with an application to MaxClique, A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases, Exact Solution of Two Location Problems via Branch-and-Bound, A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints, Semidefinite programming and eigenvalue bounds for the graph partition problem, Completely positive reformulations for polynomial optimization, Exploiting symmetry in copositive programs via semidefinite hierarchies, On Degenerate Doubly Nonnegative Projection Problems, Exact SDP relaxations of quadratically constrained quadratic programs with forest structures, A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
Uses Software
Cites Work
- Unnamed Item
- QAPLIB-A quadratic assignment problem library
- A survey for the quadratic assignment problem
- Bounds for the quadratic assignment problem using the bundle method
- Ranking scalar products to improve bounds for the quadratic assignment problem
- The quadratic assignment problem. Theory and algorithms
- Semidefinite programming relaxations for the quadratic assignment problem
- Recent advances in the solution of quadratic assignment problems
- On Lagrangian Relaxation of Quadratic Matrix Constraints
- Approximation of the Stability Number of a Graph via Copositive Programming
- Assignment Problems and the Location of Economic Activities
- Matrix Analysis
- Cones of Matrices and Set-Functions and 0–1 Optimization
- P-Complete Approximation Problems
- A spectral approach to bandwidth and separator problems in graphs
- A Copositive Programming Approach to Graph Partitioning
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
