Semidefinite programming relaxations for the quadratic assignment problem
From MaRDI portal
Publication:1386486
DOI10.1023/A:1009795911987zbMath0904.90145OpenAlexW1595903022MaRDI QIDQ1386486
Qing Zhao, Franz Rendl, Henry Wolkowicz, Stefan E. Karisch
Publication date: 10 August 1998
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1009795911987
semidefinite programmingquadratic assignmentinterior-point methodslarge scale problemssemidefinite programming relaxationsSlater constraint qualificationprimal dual interior-point methods
Related Items
Copositive and semidefinite relaxations of the quadratic assignment problem, Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, Incomplete orthogonalization preconditioners for solving large and dense linear systems which arise from semidefinite programming, On semidefinite programming bounds for graph bandwidth, Convex Relaxations for Permutation Problems, Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, A survey for the quadratic assignment problem, Exact Recovery with Symmetries for the Doubly Stochastic Relaxation, A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives, A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Bounds for the quadratic assignment problem using the bundle method, Efficient random graph matching via degree profiles, Gangster operators and invincibility of positive semidefinite matrices, Efficient Use of Semidefinite Programming for Selection of Rotamers in Protein Conformations, A survey of hidden convex optimization, An exact semidefinite programming approach for the max-mean dispersion problem, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Semidefinite approximations for quadratic programs over orthogonal matrices, Lower bounds for the bandwidth problem, Strong duality and minimal representations for cone optimization, Minimum energy configurations on a toric lattice as a quadratic assignment problem, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, A note on the SDP relaxation of the minimum cut problem, A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP, Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem, Sinkhorn Algorithm for Lifted Assignment Problems, Exact SDP relaxations for quadratic programs with bipartite graph structures, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Moment inequalities for sums of random matrices and their applications in optimization, Hidden Hamiltonian Cycle Recovery via Linear Programming, Semidefinite programming relaxations for the graph partitioning problem, Quadratic Combinatorial Optimization Using Separable Underestimators, A polynomial time constraint-reduced algorithm for semidefinite optimization problems, On improving convex quadratic programming relaxation for the quadratic assignment problem, ADMM for the SDP relaxation of the QAP, Semidefinite programming approach for the quadratic assignment problem with a sparse graph, The MIN-cut and vertex separator problem, The demand weighted vehicle routing problem, Contribution of copositive formulations to the graph partitioning problem, Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems, Selected topics on assignment problems, Semidefinite programming for discrete optimization and matrix completion problems, Local minima and convergence in low-rank semidefinite programming, On self-regular IPMs (with comments and rejoinder), Effective formulation reductions for the quadratic assignment problem, Preprocessing and Regularization for Degenerate Semidefinite Programs, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, A new relaxation framework for quadratic assignment problems based on matrix splitting, Validating numerical semidefinite programming solvers for polynomial invariants, Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone, A proximal DC approach for quadratic assignment problem, A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem, Semidefinite spectral clustering, Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem, Semidefinite relaxations for partitioning, assignment and ordering problems, Relaxations of Combinatorial Problems Via Association Schemes, SDP Relaxations for Some Combinatorial Optimization Problems, An evaluation of semidefinite programming based approaches for discrete lot-sizing problems, Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting, A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices, Algorithm 996, Semidefinite relaxations for partitioning, assignment and ordering problems, Image matching from handcrafted to deep features: a survey, A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases, Exploiting special structure in semidefinite programming: a survey of theory and applications, Scalable Semidefinite Programming, Exact Solution of Two Location Problems via Branch-and-Bound, A note on lack of strong duality for quadratic problems with orthogonal constraints, A time-triggered dimension reduction algorithm for the task assignment problem, Semidefinite programming and eigenvalue bounds for the graph partition problem, On the Slater condition for the SDP relaxations of nonconvex sets, Convex graph invariant relaxations for graph edit distance
Uses Software
