{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:18:07Z","timestamp":1766135887200},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T00:00:00Z","timestamp":1195084800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s10589-007-9093-1","type":"journal-article","created":{"date-parts":[[2007,11,14]],"date-time":"2007-11-14T00:43:57Z","timestamp":1195001037000},"page":"351-372","source":"Crossref","is-referenced-by-count":47,"title":["An algorithm for the generalized quadratic assignment problem"],"prefix":"10.1007","volume":"40","author":[{"given":"Peter M.","family":"Hahn","sequence":"first","affiliation":[]},{"given":"Bum-Jin","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Monique","family":"Guignard","sequence":"additional","affiliation":[]},{"given":"J. MacGregor","family":"Smith","sequence":"additional","affiliation":[]},{"given":"Yi-Rong","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,11,15]]},"reference":[{"key":"9093_CR1","doi-asserted-by":"crossref","first-page":"1274","DOI":"10.1287\/mnsc.32.10.1274","volume":"32","author":"W.P. Adams","year":"1986","unstructured":"Adams, W.P., Sherali, H.D.: A tight linearization and an algorithm for zero-one quadratic programming problems. Manag. Sci. 32, 1274\u20131290 (1986)","journal-title":"Manag. Sci."},{"key":"9093_CR2","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1287\/opre.38.2.217","volume":"38","author":"W.P. Adams","year":"1990","unstructured":"Adams, W.P., Sherali, H.D.: Linearization strategies for a class of zero-one mixed integer programming problems. Oper. Res. 38, 217\u2013226 (1990)","journal-title":"Oper. Res."},{"key":"9093_CR3","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1016\/j.ejor.2006.03.051","volume":"180","author":"W.P. Adams","year":"2007","unstructured":"Adams, W.P., Guignard, M., Hahn, P.M., Hightower, W.L.: A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Eur. J.\u00a0Oper. Res. 180, 983\u2013996 (2007)","journal-title":"Eur. J.\u00a0Oper. Res."},{"key":"9093_CR4","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/PL00011402","volume":"89","author":"K.M. Anstreicher","year":"2001","unstructured":"Anstreicher, K.M., Brixius, N.W.: A new bound for the quadratic assignment problem based on convex quadratic programming. Math. Program. 89, 341\u2013357 (2001)","journal-title":"Math. Program."},{"key":"9093_CR5","unstructured":"Balachandran, V.: An integer generalized transportation model of optimal job assignment to computer networks. Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, Working Paper 34-72-3 (1972)"},{"key":"9093_CR6","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0167-6377(83)90035-4","volume":"2","author":"J.F. Benders","year":"1983","unstructured":"Benders, J.F., van Nunen, J.A.E.E.: A property of assignment type mixed integer linear programming problems. Oper. Res. Lett. 2, 47\u201352 (1983)","journal-title":"Oper. Res. Lett."},{"key":"9093_CR7","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1006\/jpdc.1995.1061","volume":"26","author":"A. Billionnet","year":"1995","unstructured":"Billionnet, A., Elloumi, S.: An algorithm for finding the k-best allocations of a tree structured program. J.\u00a0Parallel Distrib. Comput. 26, 225\u2013232 (1995)","journal-title":"J.\u00a0Parallel Distrib. Comput."},{"key":"9093_CR8","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0166-218X(00)00257-2","volume":"109","author":"A. Billionnet","year":"2001","unstructured":"Billionnet, A., Elloumi, S.: Best reduction of the quadratic semi-assignment problem. Discrete Appl. Math. (DAM) 109, 197\u2013213 (2001)","journal-title":"Discrete Appl. Math. (DAM)"},{"key":"9093_CR9","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1137\/040609574","volume":"16","author":"S. Burer","year":"2006","unstructured":"Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J.\u00a0Optim. 16, 726\u2013750 (2006)","journal-title":"SIAM J.\u00a0Optim."},{"key":"9093_CR10","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1287\/ijoc.1040.0128","volume":"19","author":"J.-F. Cordeau","year":"2006","unstructured":"Cordeau, J.-F., Gaudioso, M., Laporte, G., Moccia, L.: A memetic heuristic for the generalized quadratic assignment problem. INFORMS J.\u00a0Comput. 19, 433\u2013443 (2006)","journal-title":"INFORMS J.\u00a0Comput."},{"key":"9093_CR11","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/S0377-2217(00)00108-9","volume":"132","author":"J.A. Diaz","year":"2001","unstructured":"Diaz, J.A., Fernandez, E.: A tabu search heuristic for the generalized assignment problem. Eur. J.\u00a0Oper. Res. 132, 22\u201338 (2001)","journal-title":"Eur. J.\u00a0Oper. Res."},{"key":"9093_CR12","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10479-005-3444-z","volume":"139","author":"Z. Drezner","year":"2005","unstructured":"Drezner, Z., Hahn, P.M., Taillard, E.: Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Ann. Oper. Res. 139, 65\u201394 (2005)","journal-title":"Ann. Oper. Res."},{"key":"9093_CR13","unstructured":"Elloumi, S.: The task assignment problem and the constrained task assignment problem. Instances and Solution files, 2003. Available at: http:\/\/cedric.cnam.fr\/oc\/TAP\/TAP.html"},{"key":"9093_CR14","unstructured":"Elloumi, S., Roupin, F., Soutif, E.: Comparison of different lower bounds for the constrained module allocation problem. Technical Report TR CEDRIC No 473 (2003)"},{"key":"9093_CR15","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/net.3230110205","volume":"11","author":"M.L. Fisher","year":"1981","unstructured":"Fisher, M.L., Jaikumar, R.: A generalized assignment heuristic for vehicle routing. Networks 11, 109\u2013124 (1981)","journal-title":"Networks"},{"key":"9093_CR16","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1287\/mnsc.32.9.1095","volume":"32","author":"M.L. Fisher","year":"1986","unstructured":"Fisher, M.L., Jaikumar, R., Van Wassenhove, L.N.: A multiplier adjustment method for the generalized assignment problem. Manag. Sci. 32, 1095\u20131103 (1986)","journal-title":"Manag. Sci."},{"key":"9093_CR17","unstructured":"Grant, T.L.: An evaluation and analysis of the resolvent sequence method for solving the quadratic assignment problem. Master\u2019s Thesis, Dept. of Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104 (1989)"},{"key":"9093_CR18","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1287\/opre.37.4.658","volume":"37","author":"M. Guignard","year":"1989","unstructured":"Guignard, M., Rosenwein, M.: An improved dual-based algorithm for the generalized assignment problem. Oper. Res. 37, 658\u2013663 (1989)","journal-title":"Oper. Res."},{"key":"9093_CR19","unstructured":"Guignard, M., Hahn, P.M., Ding, Z.: Hybrid ARQ symbol mapping in digital wireless communication systems based on the quadratic 3-dimensional assignment problem (Q3AP). NSF Grant: DMI-0400155 (2004)"},{"key":"9093_CR20","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1287\/opre.46.6.912","volume":"46","author":"P.M. Hahn","year":"1998","unstructured":"Hahn, P.M., Grant, T.L.: Lower bounds for the quadratic assignment problem based upon a dual formulation. Oper. Res. 46, 912\u2013922 (1998)","journal-title":"Oper. Res."},{"key":"9093_CR21","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1023\/A:1012252420779","volume":"12","author":"P.M. Hahn","year":"2001","unstructured":"Hahn, P.M., Krarup, J.: A hospital facility problem finally solved. J.\u00a0Intell. Manuf. 12, 487\u2013496 (2001)","journal-title":"J.\u00a0Intell. Manuf."},{"key":"9093_CR22","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/S0377-2217(97)00063-5","volume":"108","author":"P.M. Hahn","year":"1998","unstructured":"Hahn, P.M., Grant, T.L., Hall, N.: A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method. Eur. J.\u00a0Oper. Res. 108, 629\u2013640 (1998)","journal-title":"Eur. J.\u00a0Oper. Res."},{"key":"9093_CR23","first-page":"41","volume":"11","author":"P.M. Hahn","year":"2001","unstructured":"Hahn, P.M., Hightower, W.L., Johnson, T.A., Guignard-Spielberg, M., Roucairol, C.: Tree elaboration strategies in branch-and-bound algorithms for solving the quadratic assignment problem. Yugosl. J.\u00a0Oper. Res. 11, 41\u201360 (2001)","journal-title":"Yugosl. J.\u00a0Oper. Res."},{"key":"9093_CR24","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0377-2217(86)90328-0","volume":"27","author":"K. J\u00f6rnsten","year":"1986","unstructured":"J\u00f6rnsten, K., N\u00e4sberg, M.: A new Lagrangean-relaxation approach to the generalized assignment problem. Eur. J.\u00a0Oper. Res. 27, 313\u2013323 (1986)","journal-title":"Eur. J.\u00a0Oper. Res."},{"key":"9093_CR25","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s006070050040","volume":"63","author":"S.E. Karisch","year":"1999","unstructured":"Karisch, S.E., \u00c7ela, E., Clausen, J., Espersen, T.: A dual framework for lower bounds of the quadratic assignment problem based on linearization. Computing 63, 351\u2013403 (1999)","journal-title":"Computing"},{"key":"9093_CR26","unstructured":"Kim, B.-J.: Investigation of methods for solving new classes of quadratic assignment problems (QAPs). PhD thesis, Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104 (May 2006)"},{"key":"9093_CR27","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/0377-2217(93)E0174-V","volume":"82","author":"M. Laguna","year":"1995","unstructured":"Laguna, M., Kelly, J.P., Gonz\u00e1lez-Velarde, J.L., Glover, F.: Tabu search for the multilevel generalized assignment problem. Eur. J.\u00a0Oper. Res. 82, 176\u2013189 (1995)","journal-title":"Eur. J.\u00a0Oper. Res."},{"key":"9093_CR28","unstructured":"Lee, C.-G., Ma, Z.: The generalized quadratic assignment problem. Research Report, Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario, M5S 3G8, Canada (2004)"},{"key":"9093_CR29","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/j.ejor.2005.09.032","volume":"176","author":"E.M. Loiola","year":"2007","unstructured":"Loiola, E.M., de Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P.M., Querido, T.: A survey for the quadratic assignment problem. Invit. Rev. Eur. J.\u00a0Oper. Res. 176, 657\u2013690 (2007)","journal-title":"Invit. Rev. Eur. J.\u00a0Oper. Res."},{"key":"9093_CR30","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0167-6377(92)90015-U","volume":"12","author":"V.F. Magirou","year":"1992","unstructured":"Magirou, V.F.: An improved partial solution to the task assignment and multiway cut problems. Oper. Res. Lett. 12, 3\u201310 (1992)","journal-title":"Oper. Res. Lett."},{"key":"9093_CR31","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/0167-6377(89)90022-9","volume":"8","author":"V.F. Magirou","year":"1989","unstructured":"Magirou, V.F., Milis, J.Z.: An algorithm for the multiprocessor assignment problem. Oper. Res. Lett. 8, 351\u2013356 (1989)","journal-title":"Oper. Res. Lett."},{"key":"9093_CR32","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S. Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990)"},{"key":"9093_CR33","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1142\/9789812778215_0019","volume-title":"Combinatorial and Global Optimization","author":"K.G. Ramakrishnan","year":"2002","unstructured":"Ramakrishnan, K.G., Resende, M.G.C., Ramachandran, B., Pekny, J.F.: Tight QAP bounds via linear programming. In: Pardalos, P.M., Migdalas, A., Burkard, E. (eds.) Combinatorial and Global Optimization, pp. 297\u2013303. World Scientific, Republic of Singapore (2002)"},{"key":"9093_CR34","unstructured":"Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Accepted to Mathematical Programming. Available at http:\/\/www.springerlink.com\/content\/a878n099r184510g\/"},{"key":"9093_CR35","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1287\/opre.43.5.781","volume":"43","author":"M.G.C. Resende","year":"1995","unstructured":"Resende, M.G.C., Ramakrishnan, K.G., Drezner, Z.: Computing lower bounds for the quadratic assignment with an interior point algorithm for linear programming. Oper. Res. 43, 781\u2013791 (1995)","journal-title":"Oper. Res."},{"key":"9093_CR36","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0166-218X(99)00224-3","volume":"103","author":"H.E. Romeijn","year":"2000","unstructured":"Romeijn, H.E., Morales, D.R.: A class of greedy algorithms for the generalized assignment problem. Discrete Appl. Math. 103, 209\u2013235 (2000)","journal-title":"Discrete Appl. Math."},{"key":"9093_CR37","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF01580430","volume":"8","author":"G.T. Ross","year":"1975","unstructured":"Ross, G.T., Soland, R.M.: A branch-and-bound algorithm for the generalized assignment problem. Math. Program. 8, 91\u2013103 (1975)","journal-title":"Math. Program."},{"key":"9093_CR38","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/s10878-004-4838-6","volume":"8","author":"F. Roupin","year":"2004","unstructured":"Roupin, F.: From linear to semi-definite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems. J.\u00a0Comb. Optim. 8, 469\u2013493 (2004)","journal-title":"J.\u00a0Comb. Optim."},{"key":"9093_CR39","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.: P-complete approximation problems. J.\u00a0Assoc. Comput. Mach. 23, 555\u2013565 (1976)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"key":"9093_CR40","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1287\/opre.45.6.831","volume":"45","author":"M. Savelsbergh","year":"1997","unstructured":"Savelsbergh, M.: A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45, 831\u2013841 (1997)","journal-title":"Oper. Res."},{"key":"9093_CR41","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J.\u00a0Discrete Math. 3, 411\u2013430 (1990)","journal-title":"SIAM J.\u00a0Discrete Math."},{"key":"9093_CR42","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0166-218X(92)00190-W","volume":"52","author":"H.D. Sherali","year":"1994","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Appl. Math. 52, 83\u2013106 (1994)","journal-title":"Discrete Appl. Math."},{"key":"9093_CR43","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-4388-3","volume-title":"A Reformulation-Linearization Technique for Solving Discrete and Continuous Non-convex Problems, 1st edn","author":"H.D. Sherali","year":"1999","unstructured":"Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Non-convex Problems, 1st edn. Kluwer Academic, Norwell (1999)"},{"key":"9093_CR44","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0377-2217(92)90084-M","volume":"60","author":"S. Sofianopoulous","year":"1992","unstructured":"Sofianopoulous, S.: Simulated annealing applied to the process allocation problem. Eur. J.\u00a0Oper. Res. 60, 327\u2013334 (1992)","journal-title":"Eur. J.\u00a0Oper. Res."},{"key":"9093_CR45","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1057\/jors.1992.67","volume":"43","author":"S. Sofianopoulous","year":"1992","unstructured":"Sofianopoulous, S.: The process allocation problem: a survey of the application of graph-theoretic and integer programming approaches. J.\u00a0Oper. Res. Soc. 43, 407\u2013413 (1992)","journal-title":"J.\u00a0Oper. Res. Soc."},{"key":"9093_CR46","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1080\/10556789808805722","volume":"10","author":"M. Yagiura","year":"1998","unstructured":"Yagiura, M., Yamaguchi, T., Ibaraki, T.: A variable depth search algorithm with branching search for the generalized assignment problem. Optim. Methods Softw. 10, 419\u2013441 (1998)","journal-title":"Optim. Methods Softw."},{"key":"9093_CR47","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/978-1-4615-5775-3_31","volume-title":"Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization","author":"M. Yagiura","year":"1999","unstructured":"Yagiura, M., Yamaguchi, T., Ibaraki, T.: A variable depth search algorithm with branching search for the generalized assignment problem. In: Martello, S., Osman, I.H., Roucairol, C. (eds.) Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 459\u2013471. Kluwer Academic, Boston (1999)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-007-9093-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-007-9093-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-007-9093-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T11:36:32Z","timestamp":1559302592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-007-9093-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,15]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["9093"],"URL":"https:\/\/doi.org\/10.1007\/s10589-007-9093-1","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,15]]}}}