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

References

• 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.Crossref, Google Scholar
• 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, Google Scholar
• Anstreicher KM (2003) Recent advances in the solution of quadratic assignment problems. Math. Program. B 97:27–42.Crossref, Google Scholar
• 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, Google Scholar
• Anstreicher KM, Brixius N, Goux JP, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Math. Program. 91:563–588.Crossref, Google Scholar
• 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, Google Scholar
• Brixius NW (2000) Solving large-scale quadratic assignment problems. PhD thesis, The University of Iowa, Iowa City.Google Scholar
• Brixius NW, Anstreicher KM (2001) Solving quadratic assignment problems using convex quadratic programming relaxations. Optim. Methods Software 16:49–68.Crossref, Google Scholar
• 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, Google Scholar
• Burkard R, Dell’Amico M, Martello S (2009) Assignment Problems (SIAM, Philadelphia).Crossref, Google Scholar
• Burkard RE, Karisch SE, Rendl F (1997) QAPLIB—A quadratic assignment problem library. J. Global Optim. 10:391–403.Crossref, Google Scholar
• Clausen J, Perregaard M (1997) Solving large quadratic assignment problems in parallel. Comput. Optim. Appl. 8:111–127.Crossref, Google Scholar
• 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, Google Scholar
• de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Program. 133:75–91.Crossref, Google Scholar
• de Klerk E, Pasechnik DV, Sotirov R (2008) On semidefinite programming relaxations of the traveling salesman problem. SIAM J. Optim. 19:1559–1573.Crossref, Google Scholar
• Fischetti M, Monaci M, Salvagnin D (2012) Three ideas for the quadratic assignment problem. Oper. Res. 60:954–964.Link, Google Scholar
• Gilmore PC (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. J. Soc. Indust. Appl. Math. 10:305–313.Crossref, Google Scholar
• Gray RM (2006) Toeplitz and Circulant Matrices: A review. Foundations Trends Comm. Inform. Theory 2:155–239.Crossref, Google Scholar
• 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, Google Scholar
• 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.Google Scholar
• Held M, Karp RM (1970) The traveling-salesman problem and minimum spanning trees. Oper. Res. 18:1138–1162.Link, Google Scholar
• Koopmans TC, Beckmann MJ (1957) Assignment problems and the location of economic activities. Econometrica 25:53–76.Crossref, Google Scholar
• Lawler EL (1963) The quadratic assignment problem. Management Sci. 9:586–599.Link, Google Scholar
• 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, Google Scholar
• Nyberg A, Westerlund T (2012) A new exact discrete linear reformulation of the quadratic assignment problem. Eur. J. Oper. Res. 220:314–319.Crossref, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• Povh J, Rendl F (2009) Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6:231–241.Crossref, Google Scholar
• Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11/12:625–653.Crossref, Google Scholar
• Toh KC, Todd MJ, Tütüncü RH (1999) SDPT3—A Matlab software package for semidefinite programming. Optim. Methods Software 11:545–581.Crossref, Google Scholar
• Xia Y (2013) Convex hull of the orthogonal similarity set with applications in quadratic assignment problems. J. Indust. Management Optim. 9:687–699.Crossref, Google Scholar
• Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2:71–109.Crossref, Google Scholar