Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters

References

• Adams WP, Johnson TA (1994) Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser. Discret. Math. Theor. Comput. Sci. 16:43–77.Crossref, Google Scholar
• Adams WP, Guignard M, Peter MH, Hightower WL (2007) A level-2 reformulation–linearization technique bound for the Quadratic Assignment Problem. Eur. J. Oper. Res. 180(3):983–996.Crossref, Google Scholar
• Anstreicher K, Brixius N, Goux J-P, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Math. Programming 91(3):563–588.Crossref, Google Scholar
• Burer S, Vandenbussche D (2006) Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3):726–750.Crossref, Google Scholar
• Burkard RE, Cela E, Pardalos PM, Pitsoulis LS (1998) The quadratic assignment problem. Du DZ, Pardalos PM, eds. Handbook of Combinatorial Optimization (Springer, Boston), 1713–1809.Crossref, Google Scholar
• Burkard RE, Karisch SE, Rendl F (1997) QAPLIB–A quadratic assignment problem library. J. Global Optim. 10(4):391–403.Crossref, Google Scholar
• Clausen J, Perregaard M (1997) Solving large quadratic assignment problems in parallel. Comput. Optim. Appl. 8(2):111–127.Crossref, Google Scholar
• Date K, Nagi R (2016) GPU-accelerated Hungarian algorithms for the linear assignment problem. Parallel Comput. 57:52–72.Crossref, Google Scholar
• Frieze AM, Yadegar J (1983) On the quadratic assignment problem. Discrete Appl. Math. 5(1):89–98.Crossref, Google Scholar
• Geoffrion AM (1974) Lagrangean relaxation for integer programming. Balinski ML, ed. Approaches to Integer Programming, Mathematical Programming Studies, vol 2. (Springer, Berlin), 82–114.Crossref, Google Scholar
• Gonçalves AD, Pessoa AA, Bentes C, Farias R, Drummond LM (2017) A graphics processing unit algorithm to solve the quadratic assignment problem using level-2 reformulation-linearization technique. INFORMS J. Comput. 29(4):676–687.Link, Google Scholar
• Hahn P, Grant T (1998) Lower bounds for the Quadratic Assignment Problem based upon a dual formulation. Oper. Res. 46(6):912–922.Link, Google Scholar
• Hahn P, Roth A, Saltzman M, Guignard M (2013) Memory-aware parallelized RLT3 for solving quadratic assignment problems. Optimization Online. Accessed June 23, 2016, http://www.optimization-online.org/DB_FILE/2013/12/4144.pdf.Google Scholar
• Hahn PM, Zhu Y-R, Guignard M, MacGregor Smith J (2010) Exact solution of emerging quadratic assignment problems. Internat. Trans. Oper. Res. 17(5):525–552.Crossref, Google Scholar
• Hahn PM, Zhu Y-R, Guignard M, Hightower WL, Saltzman MJ (2012) A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS J. Comput. 24(2):202–209.Link, Google Scholar
• Karisch SE, Rendl F (1995) Lower bounds for the quadratic assignment problem via triangle decompositions. Math. Programming 71(2):137–151.Crossref, Google Scholar
• Kaufman L, Broeckx F (1978) An algorithm for the quadratic assignment problem using bender’s decomposition. Eur. J. Oper. Res. 2(3):207–211.Crossref, Google Scholar
• Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica J. Econometric Soc. 25(1):53–76.Crossref, Google Scholar
• Lawler EL (1963) The quadratic assignment problem. Management Sci. 9(4):586–599.Link, Google Scholar
• Loiola EM, Maia De Abreu NM, Boaventura-Netto PO, Hahn P, Querido T (2007) A survey for the quadratic assignment problem. Eur. J. Oper. Res. 176(2):657–690.Crossref, Google Scholar
• Pardalos PM, Crouse JV (1989) A parallel algorithm for the quadratic assignment problem. Proc. 1989 ACM/IEEE Conf. (Institute of Electrical and Electronics Engineers, Washington, DC), 351–360.Crossref, Google Scholar
• Peng J, Zhu T, Luo H, Toh K-C (2015) Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting. Comput. Optim. Appl. 60(1):171–198.Crossref, Google Scholar
• Ramachandran B, Pekny JF (1996) Dynamic matrix factorization methods for using formulations derived from higher order lifting techniques in the solution of the Quadratic Assignment Problem. Floudas CA, Pardalos PM, eds. State of the Art in Global Optimization (Springer, Boston), 75–92.Crossref, Google Scholar
• Ramakrishnan KG, Resende MG, Ramachandran B, Pekny JF (2002) Tight QAP bounds via linear programming. Pardalos PM, Migdalas A, Burkard RE, eds. Combinatorial and Global Optimization, Series on Applied Mathematics, vol. 14 (World Scientific Publishing, Singapore), 297–303.Crossref, Google Scholar
• Roucairol C (1987) A parallel branch and bound algorithm for the quadratic assignment problem. Discrete Appl. Math. 18(2):211–225.Crossref, Google Scholar
• Sahni S, Gonzalez T (1976) P-complete approximation problems. J. ACM 23(3):555–565.Crossref, Google Scholar