{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:09:40Z","timestamp":1743048580246,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031577116"},{"type":"electronic","value":"9783031577123"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-57712-3_9","type":"book-chapter","created":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T18:02:14Z","timestamp":1713463334000},"page":"129-145","source":"Crossref","is-referenced-by-count":1,"title":["Where the\u00a0Really Hard Quadratic Assignment Problems Are: The QAP-SAT Instances"],"prefix":"10.1007","author":[{"given":"S\u00e9bastien","family":"Verel","sequence":"first","affiliation":[]},{"given":"Sarah L.","family":"Thomson","sequence":"additional","affiliation":[]},{"given":"Omar","family":"Rifki","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"17","key":"9_CR1","doi-asserted-by":"publisher","first-page":"e6321","DOI":"10.1002\/cpe.6321","volume":"33","author":"T Achary","year":"2021","unstructured":"Achary, T., Pillay, S., Pillai, S.M., Mqadi, M., Genders, E., Ezugwu, A.E.: A performance study of meta-heuristic approaches for quadratic assignment problem. Concurr. Comput.: Pract. Experience 33(17), e6321 (2021)","journal-title":"Concurr. Comput.: Pract. Experience"},{"issue":"10","key":"9_CR2","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1016\/S0305-0548(99)00067-2","volume":"27","author":"RK Ahuja","year":"2000","unstructured":"Ahuja, R.K., Orlin, J.B., Tiwari, A.: A greedy genetic algorithm for the quadratic assignment problem. Comput. Oper. Res. 27(10), 917\u2013934 (2000)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"9_CR3","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1016\/j.eswa.2014.08.011","volume":"42","author":"U Benlic","year":"2015","unstructured":"Benlic, U., Hao, J.K.: Memetic search for the quadratic assignment problem. Expert Syst. Appl. 42(1), 584\u2013595 (2015)","journal-title":"Expert Syst. Appl."},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/S0378-4371(02)00516-2","volume":"306","author":"G Biroli","year":"2002","unstructured":"Biroli, G., Cocco, S., Monasson, R.: Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem. Phys. A 306, 381\u2013394 (2002)","journal-title":"Phys. A"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Buhmann, J.M., Dumazert, J., Gronskiy, A., Szpankowski, W.: Phase transitions in parameter rich optimization problems. In: 2017 Proceedings of the Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 148\u2013155. SIAM (2017)","DOI":"10.1137\/1.9781611974775.15"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1023\/A:1008293323270","volume":"10","author":"RE Burkard","year":"1997","unstructured":"Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB-a quadratic assignment problem library. J. Global Optim. 10, 391\u2013403 (1997)","journal-title":"J. Global Optim."},{"key":"9_CR7","unstructured":"Cheeseman, P.C., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: IJCAI, vol.\u00a091, pp. 331\u2013337 (1991)"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Chicano, F., Luque, G., Alba, E.: Elementary landscape decomposition of the quadratic assignment problem. In: Proceedings of the 12th annual conference on Genetic and evolutionary computation, pp. 1425\u20131432 (2010)","DOI":"10.1145\/1830483.1830745"},{"key":"9_CR9","unstructured":"Commander, C.W.: A survey of the quadratic assignment problem, with applications (2005)"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Daolio, F., Verel, S., Ochoa, G., Tomassini, M.: Local optima networks of the quadratic assignment problem. In: IEEE Congress on Evolutionary Computation, pp.\u00a01\u20138. IEEE (2010)","DOI":"10.1109\/CEC.2010.5586481"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10479-005-3444-z","volume":"139","author":"Z Drezner","year":"2005","unstructured":"Drezner, Z., Hahn, P.M., Taillard, \u00c9.D.: 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":"9_CR12","doi-asserted-by":"crossref","unstructured":"Elorza, A., Hernando, L., Lozano, J.A.: Characterizing permutation-based combinatorial optimization problems in fourier space. Evol. Comput., 1\u201339 (2022)","DOI":"10.1109\/TEVC.2024.3457268"},{"key":"9_CR13","unstructured":"Fujii, K., Ito, N., Kim, S., Kojima, M., Shinano, Y., Toh, K.C.: Solving challenging large scale QAPs. arXiv preprint: arXiv:2101.09629 (2021)"},{"key":"9_CR14","unstructured":"Gent, I.P., Walsh, T.: The sat phase transition. In: ECAI, vol.\u00a094, pp. 105\u2013109. PITMAN (1994)"},{"issue":"1\u20132","key":"9_CR15","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/S0004-3702(96)00030-6","volume":"88","author":"IP Gent","year":"1996","unstructured":"Gent, I.P., Walsh, T.: The TSP phase transition. Artif. Intell. 88(1\u20132), 349\u2013358 (1996)","journal-title":"Artif. Intell."},{"issue":"2","key":"9_CR16","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0110022","volume":"10","author":"PC Gilmore","year":"1962","unstructured":"Gilmore, P.C.: Optimal and suboptimal algorithms for the quadratic assignment problem. J. Soc. Ind. Appl. Math. 10(2), 305\u2013313 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"9_CR17","volume-title":"Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics","author":"AK Hartmann","year":"2006","unstructured":"Hartmann, A.K., Weigt, M.: Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics. John Wiley & Sons, Hoboken (2006)"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Kondor, R.: A fourier space algorithm for solving quadratic assignment problems. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1017\u20131028. SIAM (2010)","DOI":"10.1137\/1.9781611973075.82"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica: J. Econometric Soc., 53\u201376 (1957)","DOI":"10.2307\/1907742"},{"issue":"1","key":"9_CR20","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.: The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure. Oper. Res. Lett. 43(1), 103\u2013109 (2015)","journal-title":"Oper. Res. Lett."},{"issue":"5","key":"9_CR21","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1145\/2594413.2594424","volume":"57","author":"K Leyton-Brown","year":"2014","unstructured":"Leyton-Brown, K., Hoos, H.H., Hutter, F., Xu, L.: Understanding the empirical hardness of NP-complete problems. Commun. ACM 57(5), 98\u2013107 (2014)","journal-title":"Commun. ACM"},{"issue":"2","key":"9_CR22","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/j.ejor.2005.09.032","volume":"176","author":"EM Loiola","year":"2007","unstructured":"Loiola, E.M., De Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P., Querido, T.: A survey for the quadratic assignment problem. Eur. J. Oper. Res. 176(2), 657\u2013690 (2007)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"9_CR23","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/4235.887234","volume":"4","author":"P Merz","year":"2000","unstructured":"Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. Evol. Comput. 4(4), 337\u2013352 (2000)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Monasson, R.: Introduction to phase transitions in random optimization problems. arXiv preprint: arXiv:0704.2536 (2007)","DOI":"10.1016\/S0924-8099(07)80008-4"},{"issue":"6740","key":"9_CR25","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R Monasson","year":"1999","unstructured":"Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic? Phase transitions? Nature 400(6740), 133\u2013137 (1999)","journal-title":"Nature"},{"key":"9_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-37198-1_10","volume-title":"Evolutionary Computation in Combinatorial Optimization","author":"E Pitzer","year":"2013","unstructured":"Pitzer, E., Beham, A., Affenzeller, M.: Automatic algorithm selection for the quadratic assignment problem using fitness landscape analysis. In: Middendorf, M., Blum, C. (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 7832, pp. 109\u2013120. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-3-642-37198-1_10"},{"issue":"3","key":"9_CR27","doi-asserted-by":"publisher","first-page":"1066","DOI":"10.1016\/j.ejor.2020.11.035","volume":"292","author":"A Silva","year":"2021","unstructured":"Silva, A., Coelho, L.C., Darvish, M.: Quadratic assignment problem variants: a survey and an effective parallel memetic iterated TABU search. Eur. J. Oper. Res. 292(3), 1066\u20131084 (2021)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"9_CR28","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1016\/j.cor.2011.07.006","volume":"39","author":"K Smith-Miles","year":"2012","unstructured":"Smith-Miles, K., Lopes, L.: Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. 39(5), 875\u2013889 (2012)","journal-title":"Comput. Oper. Res."},{"key":"9_CR29","doi-asserted-by":"crossref","unstructured":"Smith-Miles, K.A.: Towards insightful algorithm selection for optimisation using meta-learning concepts. In: 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), pp. 4118\u20134124. IEEE (2008)","DOI":"10.1109\/IJCNN.2008.4634391"},{"key":"9_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-3-540-24652-7_20","volume-title":"Evolutionary Computation in Combinatorial Optimization","author":"T St\u00fctzle","year":"2004","unstructured":"St\u00fctzle, T., Fernandes, S.: New benchmark instances for the QAP and the experimental analysis of algorithms. In: Gottlieb, J., Raidl, G.R. (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 3004, pp. 199\u2013209. Springer, Berlin (2004). https:\/\/doi.org\/10.1007\/978-3-540-24652-7_20"},{"issue":"4\u20135","key":"9_CR31","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/S0167-8191(05)80147-4","volume":"17","author":"\u00c9 Taillard","year":"1991","unstructured":"Taillard, \u00c9.: Robust taboo search for the quadratic assignment problem. Parallel Comput. 17(4\u20135), 443\u2013455 (1991)","journal-title":"Parallel Comput."},{"issue":"2","key":"9_CR32","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0966-8349(95)00008-6","volume":"3","author":"ED Taillard","year":"1995","unstructured":"Taillard, E.D.: Comparison of iterative searches for the quadratic assignment problem. Locat. Sci. 3(2), 87\u2013105 (1995)","journal-title":"Locat. Sci."},{"key":"9_CR33","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s12065-015-0132-z","volume":"8","author":"MH Tayarani-N","year":"2015","unstructured":"Tayarani-N, M.H., Pr\u00fcgel-Bennett, A.: Quadratic assignment problem: a landscape analysis. Evol. Intel. 8, 165\u2013184 (2015)","journal-title":"Evol. Intel."},{"key":"9_CR34","doi-asserted-by":"publisher","unstructured":"Verel, S., Daolio, F., Ochoa, G., Tomassini, M.: Sampling local optima networks of large combinatorial search spaces: the QAP case. In: Auger, A., Fonseca, C., Lourenc, N., Machado, P., Paquete, L., Whitley, D. (eds.) Parallel Problem Solving from Nature - PPSN XV. Lecture Notes in Computer Science(), vol. 11102, pp. 257\u2013268. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-99259-4_21","DOI":"10.1007\/978-3-319-99259-4_21"},{"key":"9_CR35","doi-asserted-by":"crossref","unstructured":"Vollmann, T.E., Buffa, E.S.: The facilities layout problem in perspective. Manage. Sci. 12(10), B\u2013450 (1966)","DOI":"10.1287\/mnsc.12.10.B450"},{"issue":"26","key":"9_CR36","doi-asserted-by":"publisher","first-page":"6118","DOI":"10.1103\/PhysRevLett.84.6118","volume":"84","author":"M Weigt","year":"2000","unstructured":"Weigt, M., Hartmann, A.K.: Number of guards needed by a museum: a phase transition in vertex covering of random graphs. Phys. Rev. Lett. 84(26), 6118 (2000)","journal-title":"Phys. Rev. Lett."},{"key":"9_CR37","unstructured":"Yadav, N., Murawski, C., Sardina, S., Bossaerts, P.: Phase transition in the knapsack problem. arXiv preprint: arXiv:1806.10244 (2018)"}],"container-title":["Lecture Notes in Computer Science","Evolutionary Computation in Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-57712-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T15:51:30Z","timestamp":1731772290000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57712-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031577116","9783031577123"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57712-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]}}}