×

Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting. (English) Zbl 1338.90295

Summary: 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 (see [H. Mittelmann and J. Peng, SIAM J. Optim. 20, No. 6, 3408–3426 (2010; Zbl 1211.90162)]; [J. Peng et al., Math. Program. Comput. 2, No. 1, 59–77 (2010; Zbl 1191.65071)]). 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., loc. cit.]. 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.

MSC:

90C22 Semidefinite programming
90B80 Discrete location and assignment

Software:

SDPT3; QAPLIB; CVX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, WP; Johnson, TA; Pardalos, PM (ed.); Wolkowicz, H. (ed.), Improved linear programming-based lower bounds for the quadratic assignment problem, No. 16, 43-75 (1994), Rhode Island · Zbl 0819.90049
[2] 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) · Zbl 1121.90082 · doi:10.1016/j.ejor.2006.03.051
[3] Anstreicher, K., Brixius, N.: A new lower bound via projection for the quadratic assignment problem. Math. Program. 80, 341-357 (2001) · Zbl 0986.90042 · doi:10.1007/PL00011402
[4] Ben-David, G., Malah, D.: Bounds on the performance of vector-quantizers under channel errors. IEEE Trans. Inf. Theory 51, 2227-2235 (2005) · Zbl 1285.94030 · doi:10.1109/TIT.2005.847750
[5] Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726-750 (2006) · Zbl 1113.90100 · doi:10.1137/040609574
[6] 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/ · Zbl 0884.90116
[7] Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Society for Industrial and Applied Mathematics, Philadelphia (2009) · Zbl 1196.90002 · doi:10.1137/1.9780898717754
[8] Conrad, K.: Das quadratische Zuweisungsproblem und zwei seiner Spezialfalle. Mohr Siebeck, Tubingen (1971)
[9] de Carvalho, S.A., Rahmann, S.: Microarray layout as a quadratic assignment problem. Proc. Ger. Conf. Bioinform. 83, 11-20 (2006)
[10] De 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 · doi:10.1007/s10107-008-0246-5
[11] Ding, Y., Wolkowicz, H.: A low-dimensional semidefinite relaxation for the quadratic assignment problem. Math. Oper. Res. 34, 1008-1022 (2009) · Zbl 1218.90161 · doi:10.1287/moor.1090.0419
[12] Edwards, C.: A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem. Comb. Optim. II, 35-52 (1980) · Zbl 0441.90081
[13] Gilmore, P.: Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J. Appl. Math. 10, 305-313 (1962) · Zbl 0118.15101 · doi:10.1137/0110022
[14] Grant, M., Boyd, S., Ye, Y.: CVX: Matlab software for disciplined convex programming. http://www.stanford.edu/boyd/cvx. Accessed 2013 · Zbl 1167.90009
[15] 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) · Zbl 0767.90059 · doi:10.1287/moor.17.3.727
[16] Hahn, P., Grant, T.: Lower bounds for the quadratic assignment problem based upon a dual formulation. Oper. Res. 46, 912-922 (1998) · Zbl 0979.90100
[17] 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 · Zbl 0729.90993
[18] 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) · Zbl 1465.90086 · doi:10.1287/ijoc.1110.0450
[19] Hanan, M., Kurtzberg, J.: Placement techniques. Des. Autom. Digital Syst. 1, 213-282 (1972)
[20] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[21] Jansson, C., Chaykin, D., Keil, C.: Rigorous error bounds for the optimal value in semidefinite programming. SIAM J. Numer. Anal. 46, 180-200 (2007) · Zbl 1167.90009 · doi:10.1137/050622870
[22] Koopmans, T., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica 25, 53-76 (1957) · Zbl 0098.12203 · doi:10.2307/1907742
[23] Lawler, E.: The quadratic assignment problem. Manage. Sci. 9, 589-599 (1963) · Zbl 0995.90579 · doi:10.1287/mnsc.9.4.586
[24] 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) · Zbl 1103.90058 · doi:10.1016/j.ejor.2005.09.032
[25] 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) · Zbl 1211.90162 · doi:10.1137/090748834
[26] Mukherjee, L., Singh, V., Peng, J., Xu, J., Zeitz, M., Berezney, R.: Generalized median graphs and applications. J Combin. Optim. 17, 21-44 (2009) · Zbl 1172.90497 · doi:10.1007/s10878-008-9184-7
[27] 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 · doi:10.1007/s12532-010-0012-6
[28] Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. 109, 505-524 (2007) · Zbl 1278.90303 · doi:10.1007/s10107-006-0038-8
[29] Roucairol, C.: A reduction method for quadratic assignment problems. Methods Oper. Res. 32, 185-187 (1979) · Zbl 0414.90070
[30] Taillard, E.: Comparison of iterative searches for the quadratic assignment problem. Locat. Sci. 3, 87-105 (1995) · Zbl 0916.90235 · doi:10.1016/0966-8349(95)00008-6
[31] Theobald, C.M.: An inequality for the trace of the product of two symmetric matrices. Math. Proc. Camb. Philos. Soc. 77, 77-265 (1975) · Zbl 0302.15021 · doi:10.1017/S0305004100051070
[32] Toh, K., Todd, M., Tutuncu, R.: SDPT3: Matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545-581 (1999) · Zbl 0997.90060 · doi:10.1080/10556789908805762
[33] Zhao, Q., Karisch, S., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2, 71-109 (1998) · Zbl 0904.90145 · doi:10.1023/A:1009795911987
[34] Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737-1765 (2010) · Zbl 1213.90175 · doi:10.1137/080718206
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.