Solving quadratic assignment problems using convex quadratic programming relaxations

References

• Anstreicher , K.M. 2001 . Eigenvalue bounds versus semidefinite programming for the quadratic assignment problem . SZAM J. Optimization , 11 : 254 – 265 .
   Google Scholar
• Anstreicher , K.M. and Brixius , N.W. 2001 . A new bound for the quadratic assignment problem based on convex quadratic programming . Mathematical Programming , 89 : 341 – 357 .
   Web of Science ®Google Scholar
• Anstreicher , K.M. , Brixius , N.W. , Goux , J.-P. and Linderoth , J. 2001 . Solving large quadratic assignment problems on computational grids . Mathematical Programming , to appear.
   Google Scholar
• Anstreicher , K.M. and Wolkowicz , H. 2000 . On Lagrangian relaxation of quadratic matrix constraints . SIAM J. Matrix Analysis and Applications , 22 : 41 – 55 .
   Web of Science ®Google Scholar
• Bazaraa , M.S. and Kirca , O. 1983 . A branch-and-bound based heuristic for solving the quadratic assignment problem. . Naval Research Quarterly , 30 : 287 – 304 .
   Google Scholar
• Brüingger , A. , Marzetta , A. , Clausen , J. and Perregaard , M. 1998 . Solving large-scale QAP problems in parallel with the search library ZRAM . Journal of Parallel and Distributed Computing , 50 : 157 – 169 .
   Google Scholar
• Burkard , R.E. , Çela , E. , Pardalos , P.M. and Pitsoulis , L.S. 1998 . “ The quadratic assignment problem ” . In Handbook of Combinatorial Optimization Edited by: Zhu , D.-Z. and Pardalos , P.M. Vol. 3 , Kluwer, Dordrecht
   Google Scholar
• Burkard , R. and Derigs , U. 1980 . Assignment and Matching Problems: Solution Methodr with FORTRAN Programs Berlin
   Google Scholar
• Burkard , R.E. , Karisch , S. and Rend1 , F. 1997 . QAPLIB -A quadratic assignment problem library . J. Global Optimization , 10 : 391 – 403 .
   Web of Science ®Google Scholar
• Cela , E. 1998 . The Quadratic Assignment Problem: Theory and Algorithms , Dordrecht : Kluwer .
   Google Scholar
• Clausen , J. , Karisch , S.E. , Perregaard , M. and Rend1 , F. 1998 . On the applicability of lower bounds for solving rectilinear quadratic assignment problems in parallel . Computational Optimization and Applications , 10 : 127 – 147 .
   Google Scholar
• Clausen , J. and Perregaard , M. 1997 . Solving large quadratic assignment problems in parallel . Computational Optimization and Applications , 8 : 111 – 128 .
   Google Scholar
• Crouse , J. and Pardalos , P. 1989 . “ A parallel algorithm for the quadratic assignment problem ” . In Proceedings of Supercomputing '89 , 351 – 360 . New York : ACM Press .
   Google Scholar
• Finke , G. , Burkard , R.E. and Rendl , F. 1987 . Quadratic assignment problems . Annals of Discrete Mathematics , 31 : 61 – 82 .
   Google Scholar
• Frank , M. and Wolfe , P. 1956 . An algorithm for quadratic programming . Naval Research Logistics Quarterly , 3 : 95 – 110 .
   Google Scholar
• Goux , J.-P. , Linderoth , J. and Yoder , M. 2000 . Metacomputing and the masterworker paradigm , Chicago, IL : Argonne National Laboratories . Preprint ANL/MCS-P792-0200
   Google Scholar
• Graham , A. 1981 . Kronecker Products and Matrix Calculus: with Applications , Chichester : Ellis Horwood .
   Google Scholar
• Hahn , P. and Grant , T. 1998 . Lower bounds for the quadratic assignment problem based upon a dual formulation . Operations Research , 46 : 912 – 922 .
   Web of Science ®Google Scholar
• Hahn , P. , Grant , T. and Hall , N. 1998 . A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method . European Journal of Operational Research , 108 : 629 – 440 .
   Web of Science ®Google Scholar
• Hahn , P.M. , Hightower , W.L. , Johnson , T.A. , Gugnard-Spielberg , M. and Roucairol , C. 1999 . Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem , Philadelphia, PA : Dept. of Systems Engineering, University of Pennsylvania .
   Google Scholar
• Hadley , S.W. , Rendl , F. and Wolkowicz , H. 1992 . A new lower bound via projection for the quadratic assignment problem . Mathematics of Operations Research , 17 : 727 – 739 .
   Web of Science ®Google Scholar
• Horn , R.A. and Johnson , C.R. 1991 . Topics in Matrix Analysis , Cambridge : Cambridge University Press .
   Google Scholar
• Jonker , R. and Volgenant , A. 1987 . A shortest augmenting path algorithm for dense and sparse linear assignment problems . Computing , 38 : 325 – 340 .
   Web of Science ®Google Scholar
• Kaibel , V. 2000 . “ Polyhedral Methods for the QAP ” . In Nonlinear Assignment Problems , Edited by: Pardalos , P.M. and Pitsoulis , L. Dordrecht : Kluwer .
   Google Scholar
• Karisch , S.E. , CELA , E. , Clausen , J. and Espersen , T. 1999 . A dual framework for lower bounds of the quadratic assignment problem based on linearization . Computing , 63 : 351 – 403 .
   Google Scholar
• Karisch , S.E. and Rendl , F. 1995 . Lower bounds for the quadratic assignment problem via triangle decompositions . Mathematical Programming , 71 : 137 – 152 .
   Google Scholar
• Linderoth , J.T. and Savelsbergh , M.W.P. 1999 . A computational study of search strategies in mixed integer programming . INFORMS J. Computing , 11 : 173 – 187 .
   Google Scholar
• Marzetta , A. and Briingger , A. 1999 . “ A dynamioprogramming bound for the quadratic assignment problem ” . In Lecture Notes in Computer Science Edited by: Assano , T. 339 – 348 . Berlin
   Google Scholar
• Mautor , T. and Roucairol , C. 1994 . A new exact algorithm for the solution of quadratic assignment problems . Discrete Applied Mathematics , 55 : 281 – 293 .
   Google Scholar
• Padberg M.W. Rijal M.P. Design and Integer Programming Kluwer, Dordrecht 1996
   Google Scholar
• Pardalos , P. , Rendl , F. and Wolkowicz , H. 1994 . “ The quadratic assignment problem: A survey and recent developments. ” . In Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science , Vol. 16 , 141 American Mathematical Society .
   Google Scholar
• Pardalos , P.M. , Ramakrishnan , K.G. , Resende , M.G.C. and Li , Y. 1997 . Implementation of a variance reduction-based lower bound in a branch-and bound algorithm for the quadratic assignment problem . SIAM J. Optimization , 7 : 280 – 294 .
   Google Scholar
• Stewart , D.E. and Leyk , Z. 1994 . “ Meschach: Matrix computations. InC. ” . In Proceedings of the Center for Mathematics and its Applications , Vol. 32 , The Australian National University .
   Google Scholar