Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem

DOI10.1007/s10107-008-0246-5zbMath1184.90120OpenAlexW2188609405MaRDI QIDQ847851

Renata Sotirov, Etienne de Klerk

Publication date: 19 February 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-008-0246-5

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational methods for problems pertaining to mechanics of particles and systems (70-08)

Related Items

On the tightness of SDP relaxations of QCQPs, Symmetry in Mathematical Programming, Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, On semidefinite programming bounds for graph bandwidth, Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software, A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods, Symmetry Reduction in AM/GM-Based Optimization, The Maximum k-Colorable Subgraph Problem and Related Problems, On semidefinite programming relaxations of maximum \(k\)-section, Semidefinite approximations for quadratic programs over orthogonal matrices, A new exact discrete linear reformulation of the quadratic assignment problem, Minimum energy configurations on a toric lattice as a quadratic assignment problem, Automorphisms of Rank-One Generated Hyperbolicity Cones and Their Derivative Relaxations, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, Handling symmetries in mixed-integer semidefinite programs, A numerical algorithm for block-diagonal decomposition of matrix \(*\)-algebras with application to semidefinite programming, An Algebraic Approach to Nonorthogonal General Joint Block Diagonalization, Simultaneous singular value decomposition, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, Symmetric sums of squares over \(k\)-subset hypercubes, On New Classes of Nonnegative Symmetric Tensors, DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization, Using symmetry to optimize over the Sherali-Adams relaxation, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, ADMM for the SDP relaxation of the QAP, An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming, Semidefinite programming approach for the quadratic assignment problem with a sparse graph, The MIN-cut and vertex separator problem, Symmetry in semidefinite programs, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, A new relaxation framework for quadratic assignment problems based on matrix splitting, Perturbation analysis for matrix joint block diagonalization, Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming, Alternative SDP and SOCP approximations for polynomial optimization, Relaxations of Combinatorial Problems Via Association Schemes, Copositive Programming, Invariant Semidefinite Programs, SDP Relaxations for Some Combinatorial Optimization Problems, Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Exploiting special structure in semidefinite programming: a survey of theory and applications, Symmetry Reduction to Optimize a Graph-based Polynomial From Queueing Theory, Semidefinite programming and eigenvalue bounds for the graph partition problem, Exploiting symmetry in copositive programs via semidefinite hierarchies, A dynamic inequality generation scheme for polynomial programming

Uses Software

• CSDP
• GAP
• QAPLIB
• SeDuMi
• SDPT3
• YALMIP

Cites Work

• Unnamed Item
• Unnamed Item
• Positive definite completions of partial Hermitian matrices
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Bounds for the quadratic assignment problem using the bundle method
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• Recent advances in the solution of quadratic assignment problems
• Solving large quadratic assignment problems on computational grids
• Symmetry groups, semidefinite programs, and sums of squares
• The Quadratic Assignment Problem
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• A comparison of the Delsarte and Lovász bounds
• Cones of Matrices and Set-Functions and 0–1 Optimization
• CSDP, A C library for semidefinite programming
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem