×

zbMATH — the first resource for mathematics

Semidefinite programming approach for the quadratic assignment problem with a sparse graph. (English) Zbl 1415.90071
Summary: 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 Alternating Direction Method of Multipliers 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 to tackle the assignment problem.

MSC:
90C22 Semidefinite programming
90B80 Discrete location and assignment
Software:
ADMM_QAP; SeDuMi; QAPLIB
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Aflalo, Y., Bronstein, A., Kimmel, R.: On convex relaxation of graph isomorphism. Proc. Natl. Acad. Sci. 112(10), 2942-2947 (2015). https://doi.org/10.1073/pnas.1401651112. http://www.pnas.org/content/112/10/2942.abstract · Zbl 1355.05237
[2] Alipanahi, B; Gao, X; Karakoc, E; Li, S; Balbach, F; Feng, G; Donaldson, L; Li, M, Error tolerant nmr backbone resonance assignment and automated structure generation, J. Biomol. NMR, 9, 15-41, (2011)
[3] Almohamad, H; Duffuaa, SO, A linear programming approach for the weighted graph matching problem, IEEE Trans. Pattern Anal. Mach. Intell., 15, 522-525, (1993)
[4] Babai, L.: Graph isomorphism in quasipolynomial time. ArXiv e-prints (2015)
[5] Burkard, RE; Karisch, SE; Rendl, F, QAPLIB-a quadratic assignment problemlibrary, J. Glob. Optim., 10, 391-403, (1997) · Zbl 0884.90116
[6] Cavuslar, G; Catay, B; Apaydin, MS, A tabu search approach for the nmr protein structure-based assignment problem, IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 1621-1628, (2012)
[7] Chen, C; He, B; Ye, Y; Yuan, X, The direct extension of admm for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155, 57-79, (2016) · Zbl 1332.90193
[8] Chen, L; Sun, D; Toh, KC, An efficient inexact symmetric Gauss-Seidel based majorized admm for high-dimensional convex composite conic programming, Math. Program., 161, 237-270, (2017) · Zbl 1356.90105
[9] Christofides, N., Benavent, E.: An exact algorithm for the quadratic assignment problem on a tree. Oper. Res. 37(5), 760-768 (1989). http://www.jstor.org/stable/171021 · Zbl 0682.90064
[10] Klerk, E; Sotirov, R, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Math. Program., 122, 225-246, (2010) · Zbl 1184.90120
[11] Klerk, E; Sotirov, R; Truetsch, U, A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives, INFORMS J. Comput., 27, 378-391, (2015) · Zbl 1329.90081
[12] Dufoss, F., Uar, B.: Notes on birkhoffvon neumann decomposition of doubly stochastic matrices. Linear Algebra Appl. 497, 108-115 (2016). https://doi.org/10.1016/j.laa.2016.02.023. http://www.sciencedirect.com/science/article/pii/S0024379516001257 · Zbl 1332.90193
[13] Eghbalnia, HR; Bahrami, A; Wang, L; Assadi, A; Markley, JL, Probabilistic identification of spin systems and their assignments including coil-helix inference as output (pistachio), J. Biomol. NMR, 32, 219-233, (2005)
[14] Elias Oliveira, D., Wolkowicz, H., Xu, Y.: ADMM for the SDP relaxation of the QAP. ArXiv e-prints (2015) · Zbl 0348.90152
[15] Eschermann, B., Wunderlich, H.J.: Optimized synthesis of self-testable finite state machines. In: Fault-Tolerant Computing, 1990. FTCS-20. Digest of Papers., 20th International Symposium, pp. 390-397 (1990). https://doi.org/10.1109/FTCS.1990.89393
[16] Genton, M.G.: Classes of kernels for machine learning: A statistics perspective. J. Mach. Learn. Res. 2, 299-312 (2002). http://dl.acm.org/citation.cfm?id=944790.944815 · Zbl 1037.68113
[17] Jung, YS; Zweckstetter, M, Mars—robust automatic backbone assignment of proteins, J. Biomol. NMR, 30, 11-23, (2004)
[18] Kezurer, I; Kovalsky, SZ; Basri, R; Lipman, Y, Tight relaxation of quadratic matching, Comput. Gr. Forum, (2015)
[19] Koopmans, T., Beckmann, M.J.: Assignment problems and the location of economic activities. Cowles Foundation Discussion Papers 4, Cowles Foundation for Research in Economics, Yale University (1955). http://EconPapers.repec.org/RePEc:cwl:cwldpp:4 · Zbl 1356.90105
[20] Li, X; Sun, D; Toh, KC, A Schur complement based semi-proximal admm for convex quadratic conic programming and extensions, Math. Program., 155, 333-373, (2016) · Zbl 1342.90134
[21] Loiola, E.M., de Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P., Querido, T.: A survey for the quadratic assignment problem. Eur. J. Oper. Res. 176(2), 657-690 (2007). https://doi.org/10.1016/j.ejor.2005.09.032. http://www.sciencedirect.com/science/article/pii/S0377221705008337 · Zbl 1103.90058
[22] Lyzinski, V; Fishkind, DE; Fiori, M; Vogelstein, JT; Priebe, CE; Sapiro, G, Graph matching: relax at your own risk, IEEE Trans. Pattern Anal. Mach. Intell., 38, 60, (2016)
[23] 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) · Zbl 1191.65071
[24] Peng, J; Zhu, T; Luo, H; Toh, KC, Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting, Comput. Optim. Appl., 60, 171-198, (2015) · Zbl 1338.90295
[25] Ramana, MV; Scheinerman, ER; Ullman, D, Fractional isomorphism of graphs, Discrete Math., 132, 247-265, (1994) · Zbl 0808.05077
[26] Sahni, S; Gonzalez, T, P-complete approximation problems, J. ACM, 23, 555-565, (1976) · Zbl 0348.90152
[27] Sturm, JF, Using sedumi 1.02, a Matlab toolbox for optimization over symmetric cones, Optim. Methods Softw., 11, 625-653, (1999) · Zbl 0973.90526
[28] Sun, D; Toh, KC; Yang, L, A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM J. Optim., 25, 882-915, (2015) · Zbl 1328.90083
[29] Ulrich, E.L., Akutsu, H., Doreleijers, J.F., Harano, Y., Ioannidis, Y.E., Lin, J., Livny, M., Mading, S., Maziuk, D., Miller, Z., Nakatani, E., Schulte, C.F., Tolmie, D.E., Kent Wenger, R., Yao, H., Markley, J.L.: BioMagResBank. Nucleic Acids Res. 36(suppl 1), D402-D408 (2008). https://doi.org/10.1093/nar/gkm957. http://nar.oxfordjournals.org/content/36/suppl_1/D402.abstract
[30] Wan, X; Lin, G, CISA: combined NMR resonance connectivity information determination and sequential assignment, IEEE/ACM Trans. Comput. Biol. Bioinf., 4, 336-348, (2007)
[31] Wuthrich, K., Wider, G., Wagner, G., Braun, W.: Sequential resonance assignments as a basis for determination of spatial protein structures by high resolution proton nuclear magnetic resonance. J. Mol. Biol. 155(3), 311-319 (1982). https://doi.org/10.1016/0022-2836(82)90007-9. http://www.sciencedirect.com/science/article/pii/0022283682900079 · Zbl 1338.90295
[32] Zaslavskiy, M; Bach, F; Vert, JP, A path following algorithm for the graph matching problem, IEEE Trans. Pattern Anal. Mach. Intell., 31, 2227-2242, (2009)
[33] Zhao, Q; Karisch, S; Rendl, F; Wolkowicz, H, Semidefinite programming relaxations for the quadratic assignment problem, J. Comb. Optim., 2, 71-109, (1998) · Zbl 0904.90145
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.