A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases

DOI10.1007/978-3-319-45587-7_36zbMath1445.90052OpenAlexW2508895343MaRDI QIDQ2835697

Maximilian John, Andreas Karrenbauer

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-45587-7_36

zbMATH Keywords

semidefinite programmingbranch and boundquadratic assignmentlower bound

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Uses Software

• QAPLIB
• Gurobi
• Mosek
• Biq Mac

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• A survey for the quadratic assignment problem
• A new relaxation framework for quadratic assignment problems based on matrix splitting
• Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
• On the quadratic assignment problem
• An algorithm for the quadratic assignment problem using Benders' decomposition
• Lower bounds for the quadratic assignment problem
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• Solving large quadratic assignment problems on computational grids
• The Quadratic Assignment Problem
• The Backboard Wiring Problem: A Placement Algorithm
• Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme
• Hospital Layout as a Quadratic Assignment Problem
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem

This page was built for publication: A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases