quadratic assignment problem semidefinite programming

ADMM for the SDP relaxation of the QAP

The quadratic assignment problem (QAP) is one of the hardest NP-hard discrete optimization problems. The semidefinite programming (SDP) relaxation has proven to be extremely strong for QAP by lifting the variable [1]. However, the SDP relaxation for the QAP becomes very large, and traditional methods such as the interior-point method can hardly solve problems of even medium size, say 30.

We reformulate and also strengthen the relaxation model in [1] by splitting variables and adding more constraints. Then we employ the alternating direction method of multiplier (ADMM) to solve the strengthened model with or without an additional low-rank constraint. We obtain very sharp lower bound on benchmark datasets within much shorter time compared to the best existing method.

Notation and our method

The QAP problem can be formulated as

Numerical results

We test our method on 45 benchmark QAP instances. Compared to the best existing lower bound (column 2 by Bundle method [2]), our method improves the lower bound on every instance. In addition, our method is very fast, in particular when there is a low-rank constraint (column 9).

Matlab code

Download the code

D. Oliveira, H. Wolkowicz, and Y. Xu . ADMM for the SDP relaxation of the QAP. Mathematical Programming Computation, 10(4), pp. 631–658, 2018.

• DOI: 10.1007/978-1-4757-3155-2_7
• Corpus ID: 17112637

Semidefinite Programming Approaches to the Quadratic Assignment Problem

• Henry Wolkowicz
• Published 2000
• Computer Science, Mathematics

15 Citations

A matrix-lifting semidefinite relaxation for the quadratic assignment problem ∗, a low-dimensional semidefinite relaxation for the quadratic assignment problem, semidefinite relaxation approaches for the quadratic assignment problem, improved approximation bound for quadratic optimization problems with orthogonality constraints, a survey for the quadratic assignment problem, a comprehensive review of quadratic assignment problem: variants, hybrids and applications, uma revisão comentada das abordagens do problema quadrático de alocação, semidefinite and cone programming bibliography/comments, a dynamical systems approach to weighted graph matching, sums of random symmetric matrices and applications, 46 references, bounds for the quadratic assignment problem using continuous optimization, a recipe for semidefinite relaxation for (0,1)-quadratic programming, trust regions and relaxations for the quadratic assignment problem, combining semidefinite and polyhedral relaxations for integer programs, eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem, semidefinite programming relaxation for nonconvex quadratic programs, semidefinite and lagrangian relaxations for hard combinatorial problems, on lagrangian relaxation of quadratic matrix constraints.

• Highly Influential

A New Lower Bound Via Projection for the Quadratic Assignment Problem

A new bound for the quadratic assignment problem based on convex quadratic programming, related papers.

Showing 1 through 3 of 0 Related Papers

Semidefinite programming approach for the quadratic assignment problem with a sparse graph

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options.

• Dokeroglu T Ozdemir Y (2023) A new robust Harris Hawk optimization algorithm for large quadratic assignment problems Neural Computing and Applications 10.1007/s00521-023-08387-2 35 :17 (12531-12544) Online publication date: 1-Jun-2023 https://dl.acm.org/doi/10.1007/s00521-023-08387-2
• Zhu Z Li X Wang M Zhang A (2022) Learning Markov Models Via Low-Rank Optimization Operations Research 10.1287/opre.2021.2115 70 :4 (2384-2398) Online publication date: 1-Jul-2022 https://dl.acm.org/doi/10.1287/opre.2021.2115
• Graham N Hu H Im J Li X Wolkowicz H (2022) A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP INFORMS Journal on Computing 10.1287/ijoc.2022.1161 34 :4 (2125-2143) Online publication date: 1-Jul-2022 https://dl.acm.org/doi/10.1287/ijoc.2022.1161
• Show More Cited By

Index Terms

Information systems

Data management systems

Database administration

Data dictionaries

Theory of computation

Design and analysis of algorithms

Mathematical optimization

Recommendations

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation.

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme ...

Eigenvalue Bounds Versus Semidefinite Relaxations for the Quadratic Assignment Problem

It was recently demonstrated that a well-known eigenvalue bound for the quadratic assignment problem (QAP) actually corresponds to a semidefinite programming (SDP) relaxation. However, for this bound to be computationally useful, the assignment ...

A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives

Recent progress in solving quadratic assignment problems QAPs from the QAPLIB Quadratic Assignment Problem Library test set has come from mixed-integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidefinite ...

Information

Published in.

Kluwer Academic Publishers

United States

Publication History

Author tags.

• Alternating direction method of multipliers
• Convex relaxation
• Graph matching
• Quadratic assignment problem
• Semidefinite programming

Contributors

Other metrics, bibliometrics, article metrics.

• 5 Total Citations View Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0
• Sahin M Eftekhari A Alacaoglu A Latorre F Cevher V Wallach H Larochelle H Beygelzimer A d'Alché-Buc F Fox E (2019) An inexact augmented lagrangian framework for nonconvex optimization with nonlinear constraints Proceedings of the 33rd International Conference on Neural Information Processing Systems 10.5555/3454287.3455538 (13966-13978) Online publication date: 8-Dec-2019 https://dl.acm.org/doi/10.5555/3454287.3455538
• Chen L Li X Sun D Toh K (2019) On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming Mathematical Programming: Series A and B 10.1007/s10107-019-01423-x 185 :1-2 (111-161) Online publication date: 26-Aug-2019 https://dl.acm.org/doi/10.1007/s10107-019-01423-x

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Semidefinite Programming Relaxations for the Quadratic Assignment Problem

1998, Journal of Combinatorial Optimization

Semidefinite programming(SDP) relaxations for the quadratic assignment problem (QAP)are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalentrepresentations of QAP. These relaxations result in the interesting, special, case where onlythe dual problem of the SDP relaxation has strict interior, i.e. the Slater constraint qualificationalways fails for the primal problem. Although there is no duality gap in theory,

Related Papers

Informs Journal on Computing

Renata Sotirov

Discrete Optimization

Franz Rendl

Semidefinite relaxations of the quadratic assignment problem (QAP) have recently turned out to provide good approximations to the optimal value of QAP. We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it is hard to optimize over

Mathematical Programming

Cesar Beltran-Royo

Computers & Operations Research

Miguel Fragoso Constantino

In this paper we study two formulation reductions for the quadratic assignment problem (QAP). In particular we apply these reductions to the well known Adams and Johnson [2] integer linear programming formulation of the QAP. We analyze two cases: In the first case, we study the effect of constraint reduction. In the second case, we study the effect of variable reduction in the case of a sparse cost matrix. Computational experiments with a set of 30 QAPLIB instances, which range from 12 to 32 locations, are presented. The proposed reductions turned out to be very effective.

Mathematics of Operations Research

Journal of Global Optimization

Computational Optimization and Applications

Zvi Drezner

Computational Mathematics and Mathematical Physics

Socorro Rangel , Igor Litvinchev

Computational …

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

Güneş Erdoğan

Dennis Heffley

Panos M Pardalos

European Journal of Operational Research

Cut Latifah

moustapha diaby

Luiz Antonio Nogueira Lorena

Xiaowei Bao , Nikolaos Sahinidis

International Journal of Computer Applications

Linear Algebra and its Applications

Bharat Kaku

Federico Malucelli

Francisco Chicano

Proceedings of VI ALIO/ …

Igor Litvinchev

Laila Abd, Al-Ghani, Saleh Nasser

Journal of Computer and Systems Sciences International

Miguel Mata Perez , Igor Litvinchev

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

Optimization Online

Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

• Etienne de Klerk
• Renata Sotirov

Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in: [Q. Zhao, S.E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite Programming Relaxations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization, 2,71--109, 1998.] Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in: [E. de Klerk and R. Sotirov. Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Mathematical Programming A, (to appear)]. Continuing in the same vein, we show how one may obtained stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.

CentER Discussion Paper Tilburg University, The Netherlands, September 2009.

View Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

arXiv's Accessibility Forum starts next month!

Help | Advanced Search

Mathematics > Optimization and Control

Title: semidefinite programming approach for the quadratic assignment problem with a sparse graph.

Abstract: The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension $n^2$ where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension $\mathcal{O}(n)$ no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Augmented Direction Method of Multipliers (ADMM) in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension $\mathcal{O}(n)$. The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy (NMR) to tackle the assignment problem.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

• Help & FAQ

Semidefinite programming approach for the quadratic assignment problem with a sparse graph

• Mathematics
• Center for Statistics & Machine Learning

Research output : Contribution to journal › Article › peer-review

The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension n 2 where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension O(n) no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Alternating Direction Method of Multipliers in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension O(n). The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy to tackle the assignment problem.

All Science Journal Classification (ASJC) codes

• Control and Optimization
• Computational Mathematics
• Applied Mathematics
• Alternating direction method of multipliers
• Convex relaxation
• Graph matching
• Quadratic assignment problem
• Semidefinite programming

Access to Document

• 10.1007/s10589-017-9968-8

Other files and links

• Link to publication in Scopus
• Link to the citations in Scopus

Fingerprint

• Edge Mathematics 100%
• Matrix (Mathematics) Mathematics 100%
• Sparse Graphs Mathematics 100%
• Clique Mathematics 50%
• Dual Problem Mathematics 50%
• Alternating Direction Method of Multipliers Mathematics 50%
• Running Time Mathematics 50%
• Structured Block Mathematics 50%

T1 - Semidefinite programming approach for the quadratic assignment problem with a sparse graph

AU - Bravo Ferreira, José F.S.

AU - Khoo, Yuehaw

AU - Singer, Amit

N1 - Publisher Copyright: © 2017, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2018/4/1

Y1 - 2018/4/1

N2 - The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension n2 where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension O(n) no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Alternating Direction Method of Multipliers in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension O(n). The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy to tackle the assignment problem.

AB - The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension n2 where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension O(n) no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Alternating Direction Method of Multipliers in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension O(n). The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy to tackle the assignment problem.

KW - Alternating direction method of multipliers

KW - Convex relaxation

KW - Graph matching

KW - Quadratic assignment problem

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=85034241306&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034241306&partnerID=8YFLogxK

U2 - 10.1007/s10589-017-9968-8

DO - 10.1007/s10589-017-9968-8

M3 - Article

AN - SCOPUS:85034241306

SN - 0926-6003

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options.

• Berktaş N Yaman H (2021) A Branch-and-Bound Algorithm for Team Formation on Social Networks INFORMS Journal on Computing 10.1287/ijoc.2020.1000 33 :3 (1162-1176) Online publication date: 1-Jul-2021 https://dl.acm.org/doi/10.1287/ijoc.2020.1000
• Buchheim C Traversi E (2018) Quadratic Combinatorial Optimization Using Separable Underestimators INFORMS Journal on Computing 10.1287/ijoc.2017.0789 30 :3 (424-437) Online publication date: 1-Aug-2018 https://dl.acm.org/doi/10.1287/ijoc.2017.0789
• Bravo Ferreira J Khoo Y Singer A (2018) Semidefinite programming approach for the quadratic assignment problem with a sparse graph Computational Optimization and Applications 10.1007/s10589-017-9968-8 69 :3 (677-712) Online publication date: 1-Apr-2018 https://dl.acm.org/doi/10.1007/s10589-017-9968-8
• Show More Cited By

Index Terms

Information systems

Data management systems

Database administration

Data dictionaries

Theory of computation

Design and analysis of algorithms

Mathematical optimization

Recommendations

A low-dimensional semidefinite relaxation for the quadratic assignment problem.

The quadratic assignment problem (QAP) is arguably one of the hardest NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch-and-bound ...

A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation

Let $$(MQP)$$ be a general mixed-integer quadratic program that consists of minimizing a quadratic function $$f(x) = x^TQx +c^Tx$$ subject to linear constraints. Our approach to solve $$(MQP)$$ is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem ...

On improving convex quadratic programming relaxation for the quadratic assignment problem

Relaxation techniques play a great role in solving the quadratic assignment problem, among which the convex quadratic programming bound (QPB) is competitive with existing bounds in the trade-off between cost and quality. In this article, we propose two ...

Information

Published in.

Linthicum, MD, United States

Publication History

Author tags.

• branch and bound
• convex relaxations
• quadratic assignment problem
• semidefinite programming bounds

Contributors

Other metrics, bibliometrics, article metrics.

• 6 Total Citations View Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0
• Burghard O Klein R Hullin M Klein R Schultz T Yao A (2017) Efficient lifted relaxations of the quadratic assignment problem Proceedings of the conference on Vision, Modeling and Visualization 10.2312/vmv.20171267 (119-128) Online publication date: 25-Sep-2017 https://dl.acm.org/doi/10.2312/vmv.20171267
• Evrendilek C Toroslu I Hashemikhabir S (2017) Task assignment in tree-like hierarchical structures Journal of Combinatorial Optimization 10.1007/s10878-016-0097-6 34 :2 (631-655) Online publication date: 1-Aug-2017 https://dl.acm.org/doi/10.1007/s10878-016-0097-6
• Lange M (2015) A New Matrix Splitting Based Relaxation for the Quadratic Assignment Problem Revised Selected Papers of the 6th International Conference on Mathematical Aspects of Computer and Information Sciences - Volume 9582 10.1007/978-3-319-32859-1_45 (535-549) Online publication date: 11-Nov-2015 https://dl.acm.org/doi/10.1007/978-3-319-32859-1_45

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting

• Published: 07 June 2014
• Volume 60 , pages 171–198, ( 2015 )

Cite this article

• Jiming Peng 1 ,
• Tao Zhu 2 ,
• Hezhi Luo 3 &
• Kim-Chuan Toh 4  

422 Accesses

11 Citations

Explore all metrics

Quadratic assignment problems (QAPs) are known to be among the most challenging discrete optimization problems. Recently, a new class of semi-definite relaxation models for QAPs based on matrix splitting has been proposed (Mittelmann and Peng, SIAM J Optim 20:3408–3426,  2010 ; Peng et al., Math Program Comput 2:59–77,  2010 ). In this paper, we consider the issue of how to choose an appropriate matrix splitting scheme so that the resulting relaxation model is easy to solve and able to provide a strong bound. For this, we first introduce a new notion of the so-called redundant and non-redundant matrix splitting and show that the relaxation based on a non-redundant matrix splitting can provide a stronger bound than a redundant one. Then we propose to follow the minimal trace principle to find a non-redundant matrix splitting via solving an auxiliary semi-definite programming problem. We show that applying the minimal trace principle directly leads to the so-called orthogonal matrix splitting introduced in (Peng et al., Math Program Comput 2:59–77,  2010 ). To find other non-redundant matrix splitting schemes whose resulting relaxation models are relatively easy to solve, we elaborate on two splitting schemes based on the so-called one-matrix and the sum-matrix. We analyze the solutions from the auxiliary problems for these two cases and characterize when they can provide a non-redundant matrix splitting. The lower bounds from these two splitting schemes are compared theoretically. Promising numerical results on some large QAP instances are reported, which further validate our theoretical conclusions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Semidefinite relaxations for partitioning, assignment and ordering problems.

Enhancing Semidefinite Relaxation for Quadratically Constrained Quadratic Programming via Penalty Methods

Solving nearly-separable quadratic optimization problems as nonsmooth equations.

The minimal trace principle is chosen because, as shown in our analysis in Sect.  2 , the final solution matrix following the minimal principle has the minimal rank and the rank information on the splitting matrix can be further used to reduce the memory requirement and simplify the relaxation model as discussed in Sect.  4 .

For simplicity of discussion, in all the theoretical analysis of this work, we consider only the basic model  2 which is slightly different from the full SDR model to be described in Sect.  4 . However, since in the full model we only add some convex constraints on the elements of \(Y\) , one can easily extend the results for the basic model to the full model.

We note that a similar approach (called the reduction method) has been used to improve the GLB and eigenvalue bound for QAPs with nonsymmetric matrices in the literature [ 7 , 8 , 12 , 29 ]. One simple choice is \(u=\min (B_\mathrm{off})\) . For more details on the reduction method, we refer to Sect. 7.5.2 of [ 7 ].

Adams, W.P., Johnson, T.A.: Improved linear programming-based lower bounds for the quadratic assignment problem. In: Pardalos, P.M., Wolkowicz, H. (eds.) Quadratic Assignment and Related Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, pp. 43–75. AMS, Rhode Island (1994)

Google Scholar  

Adams, W., Guignard, M., Hahn, P., Hightower, W.: A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Eur. J. Oper. Res. 180 , 983–996 (2007)

Article   MATH   MathSciNet   Google Scholar  

Anstreicher, K., Brixius, N.: A new lower bound via projection for the quadratic assignment problem. Math. Program. 80 , 341–357 (2001)

Article   MathSciNet   Google Scholar  

Ben-David, G., Malah, D.: Bounds on the performance of vector-quantizers under channel errors. IEEE Trans. Inf. Theory 51 , 2227–2235 (2005)

Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16 , 726–750 (2006)

Burkard, R., Karisch, S., Rendl, F.: QAPLIB—a quadratic assignment problem library. J. Glob. Optim. 10 , 391–403 (1997). Recent updates on QAPLIB are avaliable at http://www.seas.upenn.edu/qaplib/

Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Society for Industrial and Applied Mathematics, Philadelphia (2009)

Book   MATH   Google Scholar  

Conrad, K.: Das quadratische Zuweisungsproblem und zwei seiner Spezialfalle. Mohr Siebeck, Tubingen (1971)

de Carvalho, S.A., Rahmann, S.: Microarray layout as a quadratic assignment problem. Proc. Ger. Conf. Bioinform. 83 , 11–20 (2006)

De Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. 122 , 225–246 (2010)

Ding, Y., Wolkowicz, H.: A low-dimensional semidefinite relaxation for the quadratic assignment problem. Math. Oper. Res. 34 , 1008–1022 (2009)

Edwards, C.: A branch and bound algorithm for the Koopmans–Beckmann quadratic assignment problem. Comb. Optim. II , 35–52 (1980)

Gilmore, P.: Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J. Appl. Math. 10 , 305–313 (1962)

Grant, M., Boyd, S., Ye, Y.: CVX: Matlab software for disciplined convex programming. http://www.stanford.edu/boyd/cvx . Accessed 2013

Hadley, S.W., Rendl, F., Wolkowicz, H.: A new lower bound via projection for the quadratic assignment problem. Math. Oper. Res. 17 , 727–739 (1992)

Hahn, P., Grant, T.: Lower bounds for the quadratic assignment problem based upon a dual formulation. Oper. Res. 46 , 912–922 (1998)

Hahn, P., Anjos, M., Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB—a quadratic assignment problem library. http://www.seas.upenn.edu/qaplib/ . Accessed 2013

Hahn, P.M., Zhu, Y.R., Guignard, M., Hightower, W.L., Saltzman, M.J.: A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS J. Comput. 24 , 202–209 (2012)

Hanan, M., Kurtzberg, J.: Placement techniques. Des. Autom. Digital Syst. 1 , 213–282 (1972)

Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)

Jansson, C., Chaykin, D., Keil, C.: Rigorous error bounds for the optimal value in semidefinite programming. SIAM J. Numer. Anal. 46 , 180–200 (2007)

Koopmans, T., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica 25 , 53–76 (1957)

Lawler, E.: The quadratic assignment problem. Manage. Sci. 9 , 589–599 (1963)

Loiola, E., Abreu, N., Boaventura-Netto, P., Hahn, P., Querido, T.: A survey for the quadratic assignment problem. Eur. J. Oper. Res. 176 , 657–690 (2007)

Article   MATH   Google Scholar  

Mittelmann, H., Peng, J.: Estimating bounds for quadratic assignment problems associated with Hamming and Manhattan distance matrices based on semidefinite programming. SIAM J. Optim. 20 , 3408–3426 (2010)

Mukherjee, L., Singh, V., Peng, J., Xu, J., Zeitz, M., Berezney, R.: Generalized median graphs and applications. J Combin. Optim. 17 , 21–44 (2009)

Peng, J., Mittelmann, H., Li, X.: A new relaxation framework for quadratic assignment problems based on matrix splitting. Math. Program. Comput. 2 , 59–77 (2010)

Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. 109 , 505–524 (2007)

Roucairol, C.: A reduction method for quadratic assignment problems. Methods Oper. Res. 32 , 185–187 (1979)

Taillard, E.: Comparison of iterative searches for the quadratic assignment problem. Locat. Sci. 3 , 87–105 (1995)

Theobald, C.M.: An inequality for the trace of the product of two symmetric matrices. Math. Proc. Camb. Philos. Soc. 77 , 77–265 (1975)

Toh, K., Todd, M., Tutuncu, R.: SDPT3: Matlab software package for semidefinite programming. Optim. Methods Softw. 11 , 545–581 (1999)

Zhao, Q., Karisch, S., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2 , 71–109 (1998)

Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20 , 1737–1765 (2010)

Download references

Acknowledgments

We would like to thank the two anonymous referees and the Associate Editor for their helpful suggestions that led to substantial improvement on the presentation of the paper. We also thank Etienne de Klerk for pointing out some missing constraints in our previous implementation of the SDRMS-SUM model in CVX. This work was jointly supported by AFOSR Grant FA9550-09-1-0098 and NSF Grant DMS 09-15240 ARRA, the National Natural Science Foundation of China under Grants 11071219 and 11371324, and the Zhejiang Provincial Natural Science Foundation of China under Grant LY13A010012.

Author information

Authors and affiliations.

Department of Industrial Engineering, University of Houston, Houston, TX , 77204, USA

Jiming Peng

Department of ISE, University of Illinois at Urbana-Champaign, Champaign, IL , 61801, USA

Department of Applied Mathematics, College of Science, Zhejiang University of Technology, Hangzhou , 310032, Zhejiang, People’s Republic of China

Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore , 119076, Singapore

Kim-Chuan Toh

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Jiming Peng .

Appendix: Proofs of Theorems 2 and 3

Proof of theorem 2.

Denote the optimal solution to the MTMS-PSD problem by \((B^*_1, B^*_2)\) . We first show \((B^*_1, B^*_2)=(B^+, B^-)\) . Let \(P\) be the projection matrix defined by

It follows immediately that

where the first inequality follows from the relation

Here \(I\) denotes the identity matrix in \(\mathfrak {R}^{n\times n}\) . Similarly, one has

Therefore, we have

and the equality holds if and only if

Since all the matrices \(B_1^*, B_2^*, P\) and \( I-P\) are positive semi-definite. Relation holds if and only if

Since \(B_1^*-B_2^* = B = B^+ - B^-\) , we thus have

It remains to show that the matrix splitting \((B^+, B^-)\) is non-redundant. Suppose to the contrary that \((B^+, B^-)\) is a redundant splitting of \(B\) , i.e., there exists \(R\ne 0 \succeq 0\) such that

Then we have

which contradicts to the relation \(\mathrm{Tr}(B^+B^-)=0\) . This finishes the proof of the theorem. \(\square \)

We next cite a well-known result for matrix product from [ 31 ] that will be used in the proof of Theorem 3.

Let \(A,B\in {\textsc {S}}^n\) with the eigenvalues \(\lambda _i(A)\) and \(\lambda _i(B)\) , \(i=1,\ldots ,n\) listed in nonincreasing order. Then

where the equality holds if and only if there is an orthogonal matrix \(P\) whose columns form a common set of eigenvectors for A and B and are ordered with respect to \(\{\lambda _i(A)\}_{i=1}^n\) and \(\{\lambda _i(B)\}_{i=1}^n\) , such that \(P^{-1}AP\) and \(P^{-1}BP\) are diagonal.

Proof of Theorem 3

Since \((\alpha ,\beta )\) is an optimal solution of problem ( 23 ), there exists \(U\in {\textsc {S}}^n\) such that

From ( 42 ) to ( 44 ), we obtain directly

From ( 44 ) and ( 45 ), we follow that

This implies that \(U\) and \(\alpha E +\beta I - B\) can commute. By Theorem 1.3.12 in [ 20 ], \(U\) and \(\alpha E +\beta I - B\) are simultaneously diagonalizable. Since \(U\in {\textsc {S}}^n\) , \(\alpha E +\beta I - B\in {\textsc {S}}^n\) , there is an orthogonal matrix \(P\) such that \(P^{-1}UP\) and \(P^{-1}(\alpha E +\beta I - B)P\) are diagonal. So, we have

which in turn by ( 45 ) implies that

Due to the minimal trace principle, we have \(m=\mathrm{Rank}(\alpha E+\beta I -B) < n\) . Since \(\alpha E +\beta I - B\succeq 0\) , we assume that \(\lambda _i(\alpha E +\beta I - B)>0\) , \(i=1,\ldots ,m\) . The above equality ( 48 ) then yields \(\lambda _i(U)=0\) , \(i=1,\ldots ,m\) .

We now prove \(UE\ne EU\) . Suppose to the contrary that \(UE= EU\) . By Theorem 1.3.12 in [ 20 ], \(U\) and \(E\) are simultaneously diagonalizeable. Let

Note that the eigenvalues of \(E\) are \(0,\ldots ,0,n\) . Therefore, we have

which by ( 42 ) implies \(\lambda _n(U)=1\) . Hence, we infer from ( 49 ) that

this contradicts ( 43 ).

Because \(UE\ne EU\) , from ( 47 ) we obtain \(UB\ne BU\) . Since \(U\in {\textsc {S}}^n\) and \(B\in {\textsc {S}}^n\) , by Theorem 1.3.12 in [ 20 ], \(U\) and \(B\) are not simultaneously diagonalizable. Now using Lemma 3, we have

which, together with ( 46 ), yields

Let \(\lambda _{\max }(B)\) be the largest eigenvalue of \(B\) . Note that \(\sum _{i=1}^n\lambda _i(U)=\mathrm{Tr}(U)=n\) . Also, \(\lambda _i(U)\ge 0\) for all \(i\) since \(U\succeq 0\) . It then follows from ( 50 ) that

On the other hand, from ( 45 ), we have

This means that

If \(\alpha =0\) , then the combination of ( 51 ) and ( 52 ) leads to a contradiction.

If \(\alpha <0\) . Let \(\rho (B)\) be the spectral radius of \(B\) . Since \(B\in {\textsc {S}}^n\) is non-negative, by Theorem 8.3.1 in [ 20 ], then \(\rho (B)\) is an eigenvalue of \(B\) and there exists nontrivial \(\hat{x} \ge 0\in {\mathfrak {R}}^n\) such that \(B\hat{x}=\rho (B)\hat{x}\) . Without loss of generality, we can further assume that \(\Vert \hat{x}\Vert _2=1\) . Thus we have \(\hat{x}^TB\hat{x}=\rho (B)\) . Since \(\hat{x}\ge 0\) , it holds \(\hat{x}^T(E-I)\hat{x}\ge 0\) . It follows from ( 52 ) that

which contradicts to ( 51 ). Therefore, we can conclude \(\alpha >0\) . This finishes the proof of the theorem. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Peng, J., Zhu, T., Luo, H. et al. Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting. Comput Optim Appl 60 , 171–198 (2015). https://doi.org/10.1007/s10589-014-9663-y

Download citation

Received : 03 May 2013

Published : 07 June 2014

Issue Date : January 2015

DOI : https://doi.org/10.1007/s10589-014-9663-y

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Quadratic assignment problem (QAP)
• Semi-definite programming (SDP)
• Semi-definite relaxation (SDR)
• Matrix splitting
• Lower bound
• Find a journal
• Publish with us
• Track your research