×

zbMATH — the first resource for mathematics

ADMM for the SDP relaxation of the QAP. (English) Zbl 1411.90258
Summary: Semidefinite programming, SDP, relaxations have proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem, QAP, arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal-dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers ADMM in combination with facial reduction, FR, to solve the SDP relaxation. This first order approach allows for: inexpensive iterations, a method of cheaply obtaining low rank solutions; and a trivial way of exploiting the FR for adding cutting plane inequalities. In fact, we solve the doubly nonnegative, DNN, relaxation that includes both the SDP and all the nonnegativity constraints. When compared to current approaches and current best available bounds we obtain robustness, efficiency and improved bounds.

MSC:
90C22 Semidefinite programming
90B80 Discrete location and assignment
90C46 Optimality conditions and duality in mathematical programming
90C06 Large-scale problems in mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Anstreicher, KM, Recent advances in the solution of quadratic assignment problems, Math. Program., 97, 27-42, (2003) · Zbl 1035.90067
[2] Anstreicher, KM; Brixius, NW, A new bound for the quadratic assignment problem based on convex quadratic programming, Math. Program., 89, 341-357, (2001) · Zbl 0986.90042
[3] Bhati, RK; Rasool, A., Quadratic assignment problem and its relevance to the real world: a survey, Int. J. Comput. Appl., 96, 42-47, (2014)
[4] Birkhoff, G., Three observations on linear algebra, Univ. Nac. Tucumán. Revista A, 5, 147-151, (1946) · Zbl 0060.07906
[5] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122, (2011) · Zbl 1229.90122
[6] Burer, S.; Monteiro, RDC, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103, 427-444, (2005) · Zbl 1099.90040
[7] Burkard, RE; Karisch, S.; Rendl, F., QAPLIB-a quadratic assignment problem library, Eur. J. Oper. Res., 55, 115-119, (1991) · Zbl 0729.90993
[8] Burkard, RE; Karisch, SE; Rendl, F., QAPLIB-a quadratic assignment problem library, J. Global Optim., 10, 391-403, (1997) · Zbl 0884.90116
[9] 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
[10] Eckart, C.; Young, G., The approximation of one matrix by another of lower rank, Psychometrica, 1, 211-218, (1936) · JFM 62.1075.02
[11] Edwards, CS, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem, Math. Program. Study, 13, 35-52, (1980) · Zbl 0441.90081
[12] Golub, GH; Ye, Q., An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comput., 24, 312-334, (2002) · Zbl 1016.65017
[13] Ito, N., Kim, S., Kojima, M., Takeda, A., Toh, K.C.: Bbcpop: a sparse doubly nonnegative relaxation of polynomial optimization problems with binary, box and complementarity constraints. arXiv preprint arXiv:1804.00761 (2018)
[14] Jain, R., Yao, P.: A parallel approximation algorithm for positive semidefinite programming. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pp. 463-471. IEEE Computer Soc., Los Alamitos, CA (2011) · Zbl 1292.90227
[15] Jiang, Bo; Liu, Ya-Feng; Wen, Zaiwen, \(l_p\)-norm regularization algorithms for optimization over permutation matrices, SIAM J. Optim., 26, 2284-2313, (2016) · Zbl 1353.65055
[16] Kim, S.; Kojima, M.; Toh, K-C, A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems, Math. Program., 156, 161-187, (2016) · Zbl 1342.90123
[17] Koopmans, TC; Beckmann, MJ, Assignment problems and the location of economic activities, Econometrica, 25, 53-76, (1957) · Zbl 0098.12203
[18] Lawler, EL, The quadratic assignment problem, Manag. Sci., 9, 586-599, (1963) · Zbl 0995.90579
[19] Liao, Z.: Branch and bound via ADMM for the quadratic assignment problem. Master’s thesis, University of Waterloo (2016)
[20] Pardalos, P.; Rendl, F.; Wolkowicz, H.; Pardalos, PM (ed.); Wolkowicz, H. (ed.), The quadratic assignment problem: a survey and recent developments, 1-42, (1994), Providence, RI · Zbl 0817.90059
[21] Pardalos, P., Wolkowicz, H. (eds.).: Quadratic assignment and related problems. American Mathematical Society, Providence, RI, 1994. Papers from the workshop held at Rutgers University, New Brunswick, New Jersey, May 20-21 (1993)
[22] Pong, TK; Sun, H.; Wang, N.; Wolkowicz, H., Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem, Comput. Optim. Appl., 63, 333-364, (2016) · Zbl 1360.90263
[23] Povh, J.; Rendl, F., Copositive and semidefinite relaxations of the quadratic assignment problem, Discret. Optim., 6, 231-241, (2009) · Zbl 1167.90597
[24] Rendl, F.; Sotirov, R., Bounds for the quadratic assignment problem using the bundle method, Math. Program., 109, 505-524, (2007) · Zbl 1278.90303
[25] Toh, KC; Todd, MJ; Tütüncü, RH, SDPT3—a MATLAB software package for semidefinite programming, version 1.3., Optim. Methods Softw., 11, 545-581, (1999) · Zbl 0997.90060
[26] Wen, Z.; Goldfarb, D.; Yin, W., Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2, 203-230, (2010) · Zbl 1206.90088
[27] Yang, L.; Sun, D.; Toh, K-C, \({\rm SDPNAL}+\): a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Program. Comput., 7, 331-366, (2015) · Zbl 1321.90085
[28] Zhao, Q.; Karisch, SE; Rendl, F.; Wolkowicz, H., Semidefinite programming relaxations for the quadratic assignment problem, J. Comb. Optim., 2, 71-109, (1998) · Zbl 0904.90145
[29] Zhao, XY; Sun, D.; Toh, KC, A Newton-CG augmented lagrangian method for semidefinite programming, SIAM J. Optim., 20, 1737-1765, (2010) · Zbl 1213.90175
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.