{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:54Z","timestamp":1740122394854,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T00:00:00Z","timestamp":1685404800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T00:00:00Z","timestamp":1685404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-20-1-2072"],"award-info":[{"award-number":["N00014-20-1-2072"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,7]]},"DOI":"10.1007\/s10878-023-01044-3","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T09:04:58Z","timestamp":1685437498000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An LP-based characterization of solvable QAP instances with chess-board and graded structures"],"prefix":"10.1007","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1781-4049","authenticated-orcid":false,"given":"Lucas A.","family":"Waddell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jerry L.","family":"Phillips","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianzhu","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Swarup","family":"Dhar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"issue":"3","key":"1044_CR1","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.ejor.2006.03.051","volume":"180","author":"W Adams","year":"2007","unstructured":"Adams W, Guignard M, Hahn P, Hightower W (2007) A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Eur J Oper Res 180(3):983\u2013996","journal-title":"Eur J Oper Res"},{"key":"1044_CR2","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1090\/dimacs\/016\/02","volume":"16","author":"W Adams","year":"1994","unstructured":"Adams W, Johnson T (1994) Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser Discrete Math Theoret Comput Sci 16:43\u201375","journal-title":"DIMACS Ser Discrete Math Theoret Comput Sci"},{"issue":"1","key":"1044_CR3","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10479-005-3966-4","volume":"140","author":"W Adams","year":"2005","unstructured":"Adams W, Sherali H (2005) A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems. Ann Oper Res 140(1):21\u201347","journal-title":"Ann Oper Res"},{"issue":"10","key":"1044_CR4","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1287\/mnsc.32.10.1274","volume":"32","author":"W Adams","year":"1986","unstructured":"Adams W, Sherali H (1986) A tight linearization and an algorithm for zero-one quadratic programming problems. Manage Sci 32(10):1274\u20131290","journal-title":"Manage Sci"},{"issue":"2","key":"1044_CR5","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1287\/opre.38.2.217","volume":"38","author":"W Adams","year":"1990","unstructured":"Adams W, Sherali H (1990) Linearization strategies for a class of zero-one mixed integer programming problems. Oper Res 38(2):217\u2013226","journal-title":"Oper Res"},{"issue":"3","key":"1044_CR6","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF01581249","volume":"59","author":"W Adams","year":"1993","unstructured":"Adams W, Sherali H (1993) Mixed integer bilinear programming problems. Math Program 59(3):279\u2013305","journal-title":"Math Program"},{"key":"1044_CR7","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.disopt.2014.07.001","volume":"14","author":"W Adams","year":"2014","unstructured":"Adams W, Waddell L (2014) Linear programming insights into solvable cases of the quadratic assignment problem. Discret Optim 14:46\u201360","journal-title":"Discret Optim"},{"issue":"3","key":"1044_CR8","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s101070100255","volume":"91","author":"K Anstreicher","year":"2002","unstructured":"Anstreicher K, Brixius N, Goux J, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Math Program 91(3):563\u2013588","journal-title":"Math Program"},{"unstructured":"Burkard RE, \u00c7ela E, Demidenko V, Metelski N, Woeginger G (1997) Perspectives of easy and hard cases of the quadratic assignment problem. SFB Report 104, Institute of Mathematics, Technical University, Graz, Austria","key":"1044_CR9"},{"key":"1044_CR10","first-page":"241","volume":"3","author":"RE Burkard","year":"1998","unstructured":"Burkard RE, \u00c7ela E, Pardalos P, Pitsoulis L (1998) The quadratic assignment problem. Handb Comb Optim 3:241\u2013338","journal-title":"Handb Comb Optim"},{"issue":"1\u20132","key":"1044_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01585868","volume":"82","author":"RE Burkard","year":"1998","unstructured":"Burkard RE, \u00c7ela E, Rote G, Woeginger G (1998) The quadratic assignment problem with a monotone anti-Monge matrix and a symmetric Toeplitz matrix: easy and hard cases. Math Program 82(1\u20132):125\u2013158","journal-title":"Math Program"},{"key":"1044_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"RE Burkard","year":"1996","unstructured":"Burkard RE, Klinz B, Rudolf R (1996) Perspectives of Monge properties in optimization. Discret Appl Math 70:95\u2013161","journal-title":"Discret Appl Math"},{"key":"1044_CR13","first-page":"B121","volume":"21","author":"RE Burkard","year":"1977","unstructured":"Burkard RE, Offermann J (1977) Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme. Z Oper Res 21:B121\u2013B132","journal-title":"Z Oper Res"},{"key":"1044_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2787-6","volume-title":"The quadratic assignment problem: theory and algorithms","author":"E \u00c7ela","year":"1998","unstructured":"\u00c7ela E (1998) The quadratic assignment problem: theory and algorithms. Kluwer Academic Publishers, Dordrecht"},{"issue":"6","key":"1044_CR15","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1016\/j.orl.2012.06.005","volume":"40","author":"E \u00c7ela","year":"2012","unstructured":"\u00c7ela E, Deineko VG, Woeginger G (2012) Another well-solvable case of the QAP: Maximizing the job completion time variance. Oper Res Lett 40(6):356\u2013359","journal-title":"Oper Res Lett"},{"key":"1044_CR16","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.dam.2015.01.005","volume":"186","author":"E \u00c7ela","year":"2015","unstructured":"\u00c7ela E, Deineko VG, Woeginger G (2015) Well-solvable cases of the QAP with block-structured matrices. Discret Appl Math 186:56\u201365","journal-title":"Discret Appl Math"},{"issue":"1","key":"1044_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0167-6377(97)00047-3","volume":"22","author":"VG Deineko","year":"1998","unstructured":"Deineko VG, Woeginger G (1998) A solvable case of the quadratic assignment problem. Oper Res Lett 22(1):13\u201317","journal-title":"Oper Res Lett"},{"issue":"1","key":"1044_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0041-1647(72)90111-6","volume":"6","author":"J Dickey","year":"1972","unstructured":"Dickey J, Hopkins J (1972) Campus building arrangement using TOPAZ. Transp Res 6(1):59\u201368","journal-title":"Transp Res"},{"issue":"1","key":"1044_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1057\/jors.1977.29","volume":"28","author":"A Elshafei","year":"1977","unstructured":"Elshafei A (1977) Hospital layout as a quadratic assignment problem. Oper Res Quart 28(1):167\u2013179","journal-title":"Oper Res Quart"},{"issue":"4","key":"1044_CR20","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.disopt.2006.04.001","volume":"3","author":"G Erdo\u011fan","year":"2006","unstructured":"Erdo\u011fan G, Tansel B (2006) A note on a polynomial time solvable case of the quadratic assignment problem. Discret Optim 3(4):382\u2013384","journal-title":"Discret Optim"},{"issue":"3","key":"1044_CR21","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1016\/j.disopt.2011.03.002","volume":"8","author":"G Erdo\u011fan","year":"2011","unstructured":"Erdo\u011fan G, Tansel B (2011) Two classes of quadratic assignment problems that are solvable as linear assignment problems. Discret Optim 8(3):446\u2013451","journal-title":"Discret Optim"},{"issue":"4","key":"1044_CR22","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1287\/opre.24.4.595","volume":"24","author":"A Geoffrion","year":"1976","unstructured":"Geoffrion A, Graves G (1976) Scheduling parallel production lines with changeover costs: practical applications of a quadratic assignment\/LP approach. Oper Res 24(4):595\u2013610","journal-title":"Oper Res"},{"issue":"4","key":"1044_CR23","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1287\/ijoc.2017.0754","volume":"29","author":"AD Gon\u00e7alves","year":"2017","unstructured":"Gon\u00e7alves 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\u2013687","journal-title":"INFORMS J Comput"},{"issue":"5\u20136","key":"1044_CR24","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1023\/A:1012252420779","volume":"12","author":"PM Hahn","year":"2001","unstructured":"Hahn PM, Krarup J (2001) A hospital facility problem finally solved. J Intell Manuf 12(5\u20136):487\u2013496","journal-title":"J Intell Manuf"},{"issue":"2","key":"1044_CR25","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1287\/ijoc.1110.0450","volume":"24","author":"PM Hahn","year":"2012","unstructured":"Hahn PM, Zhu Y-R, Guignard M, Hightower W, Saltzman MJ (2012) A level-3 reformulation-linearization technique bound for the quadratic assignment problem. INFORMS J Comput 24(2):202\u2013209","journal-title":"INFORMS J Comput"},{"key":"1044_CR26","volume-title":"Mathematical optimization theory and operations research. MOTOR 2019. Lecture notes in computer science 11548","author":"M John","year":"2019","unstructured":"John M, Karrenbauer A (2019) Dynamic sparsification for quadratic assignment problems. In: Khachay M, Kochetov Y, Pardalos P (eds) Mathematical optimization theory and operations research. MOTOR 2019. Lecture notes in computer science 11548. Springer, Cham"},{"unstructured":"Johnson T (1992) New linear programming-based solution procedures for the quadratic assignment problem, PhD Dissertation, Clemson University","key":"1044_CR27"},{"issue":"4","key":"1044_CR28","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1287\/moor.1110.0509","volume":"36","author":"SN Kabadi","year":"2011","unstructured":"Kabadi SN, Punnen AP (2011) An $$O(n^4)$$ algorithm for the QAP linearization problem. Math Oper Res 36(4):754\u2013761","journal-title":"Math Oper Res"},{"issue":"1","key":"1044_CR29","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/1907742","volume":"25","author":"T Koopmans","year":"1957","unstructured":"Koopmans T, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53\u201376","journal-title":"Econometrica"},{"key":"1044_CR30","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BFb0120827","volume-title":"Mathematical programming in use","author":"J Krarup","year":"1978","unstructured":"Krarup J, Pruzan P (1978) Computer-aided layout design. In: Balinski ML, Lemarechal C (eds) Mathematical programming in use. North-Holland Publishing Company, Amsterdam, pp 75\u201394"},{"issue":"1","key":"1044_CR31","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.orl.2014.12.009","volume":"43","author":"M Laurent","year":"2015","unstructured":"Laurent M, Seminaroti M (2015) The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure. Oper Res Lett 43(1):103\u2013109","journal-title":"Oper Res Lett"},{"issue":"2","key":"1044_CR32","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/j.ejor.2005.09.032","volume":"176","author":"EM Loiola","year":"2007","unstructured":"Loiola EM, Maia de Abreu NM, Boaventura-Netto PO, Hahn PM, Querido T (2007) A survey for the quadratic assignment problem. Eur J Oper Res 176(2):657\u2013690","journal-title":"Eur J Oper Res"},{"key":"1044_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/dimacs\/016\/01","volume":"16","author":"PM Pardalos","year":"1994","unstructured":"Pardalos PM, Rendl F, Wolkowicz H (1994) The quadratic assignment problem: a survey and recent developments. DIMACS Ser Discrete Math Theoret Comput Sci 16:1\u201342","journal-title":"DIMACS Ser Discrete Math Theoret Comput Sci"},{"issue":"3","key":"1044_CR34","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.disopt.2013.02.003","volume":"10","author":"AP Punnen","year":"2013","unstructured":"Punnen AP, Kabadi SN (2013) A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems. Discret Optim 10(3):200\u2013209","journal-title":"Discret Optim"},{"issue":"1","key":"1044_CR35","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0166-218X(92)00190-W","volume":"52","author":"H Sherali","year":"1994","unstructured":"Sherali H, Adams W (1994) A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discret Appl Math 52(1):83\u2013106","journal-title":"Discret Appl Math"},{"issue":"3","key":"1044_CR36","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H Sherali","year":"1990","unstructured":"Sherali H, Adams W (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J Discret Math 3(3):411\u2013430","journal-title":"SIAM J Discret Math"},{"key":"1044_CR37","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4388-3","volume-title":"A reformulation-linearization technique for solving discrete and continuous nonconvex problems","author":"H Sherali","year":"1999","unstructured":"Sherali H, Adams W (1999) A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Kluwer Academic Publishers, Dordrecht\/Boston\/London"},{"issue":"1","key":"1044_CR38","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/1003003","volume":"3","author":"L Steinberg","year":"1961","unstructured":"Steinberg L (1961) The backboard wiring problem: a placement algorithm. SIAM Rev 3(1):37\u201350","journal-title":"SIAM Rev"},{"key":"1044_CR39","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/ange.19790910204","volume":"91","author":"I Ugi","year":"1979","unstructured":"Ugi I, Bauer J, Friedrich J, Gasteiger J, Jochum C, Schubert W (1979) Neue anwendungsgebiete f\u00fcr computer in der chemie. Angew Chem 91:99\u2013111","journal-title":"Angew Chem"},{"unstructured":"Waddell L, Adams W (2021) Characterizing linearizable QAPs by the level-1 reformulation-linearization technique, http:\/\/www.optimization-online.org\/DB_FILE\/2021\/03\/8308.pdf","key":"1044_CR40"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01044-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-023-01044-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01044-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,22]],"date-time":"2023-07-22T04:07:07Z","timestamp":1689998827000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-023-01044-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,30]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1044"],"URL":"https:\/\/doi.org\/10.1007\/s10878-023-01044-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2023,5,30]]},"assertion":[{"value":"8 May 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}}],"article-number":"114"}}