{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T04:07:04Z","timestamp":1780373224246,"version":"3.54.1"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032272416","type":"print"},{"value":"9783032272423","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27242-3_31","type":"book-chapter","created":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T03:27:40Z","timestamp":1780370860000},"page":"520-537","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Singleton Node Consistency for\u00a0Quadratic Assignment Problems in\u00a0Cost Function Networks"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-7869-0793","authenticated-orcid":false,"given":"Guidio","family":"Sewa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3549-4592","authenticated-orcid":false,"given":"David","family":"Allouche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2242-0458","authenticated-orcid":false,"given":"Simon","family":"de Givry","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3727-6698","authenticated-orcid":false,"given":"George","family":"Katsirelos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6049-3415","authenticated-orcid":false,"given":"Thomas","family":"Schiex","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,1]]},"reference":[{"issue":"3","key":"31_CR1","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.ejor.2006.03.051","volume":"180","author":"WP 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. Oper. Res. 180(3), 983\u2013996 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Allouche, D., de Givry, S., Katsirelos, G., Schiex, T., Zytnicki, M.: Anytime hybrid best-first search with tree decomposition for weighted CSP. In: Proceedings of the CP-15, pp. 12\u201328. Cork, Ireland (2015)","DOI":"10.1007\/978-3-319-23219-5_2"},{"key":"31_CR3","unstructured":"Bart\u00e1k, R., Erben, R.: A new algorithm for singleton arc consistency. FLAIRS, pp. 257\u2013262 (2004)"},{"key":"31_CR4","unstructured":"Beldjilali, A., Montalbano, P., Allouche, D., Katsirelos, G., de Givry, S.: Parallel Hybrid Best-First Search. In: Proceedings of the CP-22, vol. 235, pp. 7:1\u20137:10. Haifa, Israel (2022)"},{"issue":"1","key":"31_CR5","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10601-009-9080-5","volume":"16","author":"C Bessiere","year":"2011","unstructured":"Bessiere, C., Cardon, S., Debruyne, R., Lecoutre, C.: Efficient algorithms for singleton arc consistency. Constraints 16(1), 25\u201353 (2011)","journal-title":"Constraints"},{"issue":"1","key":"31_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.artint.2007.09.001","volume":"172","author":"C Bessiere","year":"2008","unstructured":"Bessiere, C., Debruyne, R.: Theoretical analysis of singleton arc consistency and its extensions. Artif. Intell. 172(1), 29\u201341 (2008)","journal-title":"Artif. Intell."},{"key":"31_CR7","unstructured":"Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: ECAI, vol. 16, p. 146 (2004)"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Burkard, R., Dell\u2019Amico, M., Martello, S.: Assignment problems: revised reprint. SIAM (2012)","DOI":"10.1137\/1.9781611972238"},{"key":"31_CR9","unstructured":"Claus, G., Cambazard, H., Jost, V.: Analysis of reduced costs filtering for alldifferent and minimum weight alldifferent global constraints. In: Proceedings of the 24th European Conference on Artificial Intelligence, vol. 325, pp. 323\u2013330. Santiago de Compostela, Spain (2020)"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.artint.2010.02.001","volume":"174","author":"M Cooper","year":"2010","unstructured":"Cooper, M., et al.: Soft arc consistency revisited. Artif. Intell. J. 174, 449\u2013478 (2010)","journal-title":"Artif. Intell. J."},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Cooper, M.C., de Givry, S., Schiex, T.: Valued constraint satisfaction problems. In: A Guided Tour of Artificial Intelligence Research: Volume II: AI Algorithms, pp. 185\u2013207. Springer (2020)","DOI":"10.1007\/978-3-030-06167-8_7"},{"key":"31_CR12","unstructured":"De Givry, S., Heras, F., Zytnicki, M., Larrosa, J.: Existential arc consistency: Getting closer to full arc consistency in weighted CSPs. In: IJCAI 5, 84\u201389 (2005)"},{"key":"31_CR13","unstructured":"Debruyne, R.: Optimal and suboptimal singleton arc consistency algorithms. IJCAI (2005)"},{"key":"31_CR14","unstructured":"Debruyne, R., Bessi\u00e8re, C.: Some practicable filtering techniques for the constraint satisfaction problem. In: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI 97, Nagoya, Japan, August 23\u201329, pp. 412\u2013417 (1997)"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Demirovi\u0107, E., Chu, G., Stuckey, P.J.: Solution-based phase saving for CP: a value-selection heuristic to simulate local search behavior in complete solvers. In: International Conference on Principles and Practice of Constraint Programming, pp. 99\u2013108. Springer (2018)","DOI":"10.1007\/978-3-319-98334-9_7"},{"key":"31_CR16","unstructured":"Dlask, T., Werner, T., de Givry, S.: Bounds on weighted CSPs using constraint propagation and Super-Reparametrizations. In: Proceedings of the CP-21. Montpellier, France (2021)"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10601-023-09343-6","volume":"28","author":"T Dlask","year":"2023","unstructured":"Dlask, T., Werner, T., de Givry, S.: Super-Reparametrizations of weighted CSPs: properties and optimization perspective. Constraints 28, 277\u2013319 (2023)","journal-title":"Constraints"},{"issue":"4","key":"31_CR18","doi-asserted-by":"publisher","first-page":"1085","DOI":"10.1016\/j.cor.2005.05.027","volume":"34","author":"G Erdo\u011fan","year":"2007","unstructured":"Erdo\u011fan, G., Tansel, B.: A branch-and-cut algorithm for quadratic assignment problems based on linearizations. Comput. Oper. Res. 34(4), 1085\u20131106 (2007)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"31_CR19","doi-asserted-by":"publisher","first-page":"954","DOI":"10.1287\/opre.1120.1073","volume":"60","author":"M Fischetti","year":"2012","unstructured":"Fischetti, M., Monaci, M., Salvagnin, D.: Three ideas for the quadratic assignment problem. Oper. Res. 60(4), 954\u2013964 (2012)","journal-title":"Oper. Res."},{"issue":"1","key":"31_CR20","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0166-218X(83)90018-5","volume":"5","author":"AM Frieze","year":"1983","unstructured":"Frieze, A.M., Yadegar, J.: On the quadratic assignment problem. Discret. Appl. Math. 5(1), 89\u201398 (1983)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"31_CR21","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."},{"issue":"3","key":"31_CR22","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s10601-016-9245-y","volume":"21","author":"B Hurley","year":"2016","unstructured":"Hurley, B., et al.: Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints 21(3), 413\u2013434 (2016). https:\/\/doi.org\/10.1007\/s10601-016-9245-y","journal-title":"Constraints"},{"key":"31_CR23","unstructured":"Jean-Charles, R.: Generalized arc consistency for global cardinality constraint. In: American Association for Artificial Intelligence, pp. 209\u2013215. AAAI 1996 (1996)"},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF02278710","volume":"38","author":"R Jonker","year":"1987","unstructured":"Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325\u2013340 (1987)","journal-title":"Computing"},{"issue":"1","key":"31_CR25","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1287\/opre.40.1.178","volume":"40","author":"J Kennington","year":"1992","unstructured":"Kennington, J., Wang, Z.: A shortest augmenting path algorithm for the semi-assignment problem. Oper. Res. 40(1), 178\u2013187 (1992)","journal-title":"Oper. Res."},{"key":"31_CR26","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\u20132","key":"31_CR27","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logistics Q. 2(1\u20132), 83\u201397 (1955)","journal-title":"Naval Res. Logistics Q."},{"key":"31_CR28","doi-asserted-by":"crossref","unstructured":"Lecoutre, C., Sa\u00efs, L., Tabary, S., Vidal, V.: Reasoning from last conflict(s) in constraint programming. Artif. Intell. J. 173, 1592\u20131614 (2009)","DOI":"10.1016\/j.artint.2009.09.002"},{"key":"31_CR29","unstructured":"Lecoutre, C., Cardon, S.: A greedy approach to establish singleton arc consistency. In: IJCAI, vol. 5, pp. 199\u2013204 (2005)"},{"issue":"2","key":"31_CR30","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."},{"key":"31_CR31","unstructured":"Montalbano, P.: Linear Constraints and Conflict-free Learning for Graphical Models, Universit\u00e9 de Toulouse (2023). Ph.D. thesis"},{"key":"31_CR32","doi-asserted-by":"crossref","unstructured":"Montalbano, P., de Givry, S., Katsirelos, G.: Multiple-choice knapsack constraint in graphical models. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 282\u2013299. Springer (2022)","DOI":"10.1007\/978-3-031-08011-1_19"},{"key":"31_CR33","doi-asserted-by":"crossref","unstructured":"Montalbano, P., de Givry, S., Katsirelos, G.: Virtual arc consistency for linear constraints in cost function networks. In: Proceedings of the ICTAI-25. Athens, Greece (2025)","DOI":"10.1109\/ICTAI66417.2025.00039"},{"issue":"1","key":"31_CR34","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s12532-010-0012-6","volume":"2","author":"J Peng","year":"2010","unstructured":"Peng, J., Mittelmann, H., Li, X.: A new relaxation framework for quadratic assignment problems based on matrix splitting. Math. Program. Comput. 2(1), 59\u201377 (2010)","journal-title":"Math. Program. Comput."},{"issue":"3","key":"31_CR35","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1023\/A:1020506526052","volume":"7","author":"JC R\u00e9gin","year":"2002","unstructured":"R\u00e9gin, J.C.: Cost-based arc consistency for global cardinality constraints. Constraints 7(3), 387\u2013405 (2002)","journal-title":"Constraints"},{"key":"31_CR36","unstructured":"Rossi, F., Van Beek, P., Walsh, T.: Handbook of constraint programming, Elsevier (2006)"},{"key":"31_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1007\/3-540-46135-3_56","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"M Sellmann","year":"2002","unstructured":"Sellmann, M.: An arc-consistency algorithm for the minimum weight all different constraint. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 744\u2013749. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-46135-3_56"},{"key":"31_CR38","doi-asserted-by":"crossref","unstructured":"Sewa, G., Allouche, D., de Givry, S., Katsirelos, G., Montalbano, P., Schiex, T.: Assignment problems in cost function networks. In: Proceedings of the AAAI-26. Singapore (2026)","DOI":"10.1609\/aaai.v40i17.38447"},{"key":"31_CR39","doi-asserted-by":"crossref","unstructured":"Tr\u00f6sser, F., De Givry, S., Katsirelos, G.: Relaxation-aware heuristics for exact optimization in graphical models. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 475\u2013491. Springer (2020)","DOI":"10.1007\/978-3-030-58942-4_31"},{"issue":"1\u20133","key":"31_CR40","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0743-1066(98)10006-7","volume":"37","author":"P Van Hentenryck","year":"1998","unstructured":"Van Hentenryck, P., Saraswat, V., Deville, Y.: Design, implementation, and evaluation of the constraint language cc (FD). J. Logic Program. 37(1\u20133), 139\u2013164 (1998)","journal-title":"J. Logic Program."},{"issue":"1","key":"31_CR41","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s11464-008-0010-4","volume":"3","author":"Y Xia","year":"2008","unstructured":"Xia, Y.: Gilmore-Lawler bound of quadratic assignment problem. Front. Math. China 3(1), 109\u2013118 (2008)","journal-title":"Front. Math. China"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27242-3_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T03:27:52Z","timestamp":1780370872000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27242-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032272416","9783032272423"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27242-3_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"1 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rabat","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Morocco","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 May 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/cpaior2026\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}