×

A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives. (English) Zbl 1329.90081

Summary: 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 programming (SDP) bounds for QAPs have also been studied in some detail, but their computational impact has been limited so far, mostly because of the restrictive size of the early relaxations. Some recent progress has been made by studying smaller SDP relaxations and by exploiting group symmetry in the QAP data. In this work, we introduce a new SDP relaxation, where the matrix variables are only of the order of the QAP dimension, and we show how one may exploit group symmetry in the problem data for this relaxation. We also provide a detailed numerical comparison with related bounds from the literature. In particular, we compute the best-known lower bounds for two QAPLIB instances.

MSC:

90B80 Discrete location and assignment
90C22 Semidefinite programming

Software:

SDPT3; QAPLIB; ZRAM; SeDuMi
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Adams WP, Johnson TA (1994) Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Series in Discrete Math. Theoret. Comput. Sci. 16:43-75. · Zbl 0819.90049
[2] Adams WP, Guignard M, Hahn PM, Hightower WL (2007) A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Eur. J. Oper. Res. 180:983-996. CrossRef · Zbl 1121.90082
[3] Anstreicher KM (2003) Recent advances in the solution of quadratic assignment problems. Math. Program. B 97:27-42. · Zbl 1035.90067
[4] Anstreicher KM, Brixius NW (2001) A new bound for the quadratic assignment problem based on convex quadratic programming. Math. Program. Ser. A 89:341-357. CrossRef · Zbl 0986.90042
[5] Anstreicher KM, Brixius N, Goux JP, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Math. Program. 91:563-588. CrossRef · Zbl 1030.90105
[6] Bachoc C, Gijswijt DC, Schrijver A, Vallentin F (2012) Invariant semidefinite programs. Handbook on Semidefinite, Cone and Polynomial Optimization, Anjos MF, Lasserre JB, eds. (Springer, New York), 219-269. CrossRef · Zbl 1334.90097
[7] Brixius NW (2000) Solving large-scale quadratic assignment problems. PhD thesis, The University of Iowa, Iowa City.
[8] Brixius NW, Anstreicher KM (2001) Solving quadratic assignment problems using convex quadratic programming relaxations. Optim. Methods Software 16:49-68. CrossRef · Zbl 0991.90107
[9] Brüngger A, Marzetta A, Clausen J, Perregaard M (1998) Solving large-scale QAP problems in parallel with the search library ZRAM. J. Parallel Distributed Comput. 50:157-169. CrossRef · Zbl 0909.68171
[10] Burkard R, Dell’Amico M, Martello S (2009) Assignment Problems (SIAM, Philadelphia). CrossRef
[11] Burkard RE, Karisch SE, Rendl F (1997) QAPLIB–A quadratic assignment problem library. J. Global Optim. 10:391-403. CrossRef · Zbl 0884.90116
[12] Clausen J, Perregaard M (1997) Solving large quadratic assignment problems in parallel. Comput. Optim. Appl. 8:111-127. CrossRef · Zbl 0887.90136
[13] de Klerk E, Sotirov R (2010) Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Math. Program. Ser. A 122:225-246. CrossRef · Zbl 1184.90120
[14] de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Program. 133:75-91. CrossRef · Zbl 1270.90045
[15] de Klerk E, Pasechnik DV, Sotirov R (2008) On semidefinite programming relaxations of the traveling salesman problem. SIAM J. Optim. 19:1559-1573. CrossRef · Zbl 1196.90094
[16] Fischetti M, Monaci M, Salvagnin D (2012) Three ideas for the quadratic assignment problem. Oper. Res. 60:954-964. Abstract, · Zbl 1260.90117
[17] Gilmore PC (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. J. Soc. Indust. Appl. Math. 10:305-313. CrossRef · Zbl 0118.15101
[18] Gray RM (2006) Toeplitz and Circulant Matrices: A review. Foundations Trends Comm. Inform. Theory 2:155-239. CrossRef
[19] Hahn PM, Grant T, Hall N (1998) A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method. Eur. J. Oper. Res. 108:629-640. CrossRef · Zbl 0947.90129
[20] Hahn PM, Hightower WL, Johnson TA, Guignard-Spielberg M, Roucairol C (2001) Tree elaboration strategies in branch-and-bound algorithms for solving the quadratic assignment problem. Yugoslav J. Oper. Res. 11:41-60.
[21] Held M, Karp RM (1970) The traveling-salesman problem and minimum spanning trees. Oper. Res. 18:1138-1162. Abstract, · Zbl 0226.90047
[22] Koopmans TC, Beckmann MJ (1957) Assignment problems and the location of economic activities. Econometrica 25:53-76. CrossRef · Zbl 0098.12203
[23] Lawler EL (1963) The quadratic assignment problem. Management Sci. 9:586-599. Abstract, · Zbl 0995.90579
[24] Mittelmann H, Peng J (2010) Estimating bounds for quadratic assignment problems associated with Hamming and Manhattan distance matrices based on semidefinite programming. SIAM J. Optim. 20:3408-3426. CrossRef · Zbl 1211.90162
[25] Nyberg A, Westerlund T (2012) A new exact discrete linear reformulation of the quadratic assignment problem. Eur. J. Oper. Res. 220:314-319. CrossRef · Zbl 1253.90140
[26] Peng J, Mittelmann H, Li X (2010) A new relaxation framework for quadratic assignment problems based on matrix splitting. Math. Program. Comput. 2:59-77. CrossRef · Zbl 1191.65071
[27] Peng J, Zhu T, Luo H, Toh KC (2015) Semi-definite relaxation of quadratic assignment problems based on nonredundant matrix splitting. Comput. Optim. Appl. 60(1):171-198. CrossRef · Zbl 1338.90295
[28] Povh J, Rendl F (2009) Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6:231-241. CrossRef · Zbl 1167.90597
[29] Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11/12:625-653. CrossRef · Zbl 0973.90526
[30] Toh KC, Todd MJ, Tütüncü RH (1999) SDPT3–A Matlab software package for semidefinite programming. Optim. Methods Software 11:545-581. CrossRef · Zbl 0997.90060
[31] Xia Y (2013) Convex hull of the orthogonal similarity set with applications in quadratic assignment problems. J. Indust. Management Optim. 9:687-699. CrossRef
[32] Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2:71-109. CrossRef · 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. 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.