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 (47)

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

This page was built for publication: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem