{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:29:03Z","timestamp":1743046143987,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031264375"},{"type":"electronic","value":"9783031264382"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,23]],"date-time":"2023-02-23T00:00:00Z","timestamp":1677110400000},"content-version":"vor","delay-in-days":53,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Preprocessing constraint satisfaction problems is a much studied method for improving the performance of subsequent solution search. The traditional explanation for its beneficial effects is \u201cproblem reduction\u201d, where possible values that cannot take part in a solution are discarded, leaving fewer possibilities to explore during search. Here, we show that this is not the only or even the main factor when dynamic variable ordering heuristics are used. Multiple lines of evidence indicate that under these conditions domain reductions effected by preprocessing serve to inform the heuristic as to which variables should be chosen for instantiation before others. It is suggested that an information transmission model is needed to account for such effects, and it is argued that an extension of this approach can incorporate simple domain reduction effects as well.<\/jats:p>","DOI":"10.1007\/978-3-031-26438-2_33","type":"book-chapter","created":{"date-parts":[[2023,2,22]],"date-time":"2023-02-22T06:32:56Z","timestamp":1677047576000},"page":"423-436","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Explaining the\u00a0Effects of\u00a0Preprocessing on\u00a0Constraint Satisfaction Search"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3537-7719","authenticated-orcid":false,"given":"Richard J.","family":"Wallace","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,23]]},"reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"Bessi\u00e8re, C.: Constraint propagation. In: Handbook of Constraint Programming, chap. 3, pp. 29\u201383. Elsevier (2006)","DOI":"10.1016\/S1574-6526(06)80007-6"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10601-009-9080-5","volume":"16","author":"C Bessi\u00e8re","year":"2011","unstructured":"Bessi\u00e8re, C., Cardon, S., Debruyne, R., Lecoutre, C.: Efficient algorithms for singleton arc consistency. Constraints 16, 25\u201353 (2011)","journal-title":"Constraints"},{"key":"33_CR3","unstructured":"Debruyne, R., Bessi\u00e8re, C.: Some practicable filtering techniques for the constraint satisfaction problem. In: Fifteenth International Joint Conference on Artifcial Intelligence - IJCAI 1997, vol. 1, pp. 412\u2013417. Morgan Kaufmann (1997)"},{"key":"33_CR4","volume-title":"Constraint Processing","author":"R Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, Burlington (2003)"},{"key":"33_CR5","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1287\/opre.39.3.378","volume":"39","author":"DS Johnson","year":"1991","unstructured":"Johnson, D.S., Aragon, C.R., McGeoch, L.A., Shevron, C.: Optimization by simulated annealing: an experimental evaluation. Part II. Graph coloring and number partitioning. Oper. Res. 39, 378\u2013406 (1991)","journal-title":"Oper. Res."},{"issue":"1","key":"33_CR6","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A Mackworth","year":"1977","unstructured":"Mackworth, A.: Consistency in networks of relations. Artif. Intell. 8(1), 99\u2013118 (1977)","journal-title":"Artif. Intell."},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Sabin, D., Freuder, E.: Contradicting conventional wisdom in constraint satisfaction. In: Proceedings of the Eleventh European Conference on Artificial Intelligence-ECAI 1994, pp. 125\u2013129. Wiley (1994)","DOI":"10.1007\/3-540-58601-6_86"},{"key":"33_CR8","volume-title":"Statistical Methods","author":"GW Snedecor","year":"1980","unstructured":"Snedecor, G.W., Cochran, W.G.: Statistical Methods, 7th edn. Iowa State University, Ames (1980)","edition":"7"},{"key":"33_CR9","unstructured":"Tsang, E.: Foundations of Constraint Satisfaction. Academic Press (1993)"},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"Wallace, R.J.: Light-weight versus heavy-weight algorithms for SAC and neighbourhood SAC. In: Russell, I., Eberle, W. (eds.) Twenty-Eighth International Florida Artificial Intelligence Research Society Conference - FLAIRS-28, pp. 91\u201396. AAAI Press (2015)","DOI":"10.3233\/AIC-140635"},{"key":"33_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.3233\/AIC-140635","volume":"28","author":"RJ Wallace","year":"2015","unstructured":"Wallace, R.J.: SAC and neighbourhood SAC. AI Commun. 28, 345\u2013364 (2015)","journal-title":"AI Commun."},{"key":"33_CR12","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-030-77091-4_19","volume-title":"AIxIA 2020 \u2013 Advances in Artificial Intelligence","author":"Richard J. Wallace","year":"2021","unstructured":"Wallace, Richard J..: Interleaving levels of consistency enforcement for singleton arc consistency in CSPs, with a new best (N)SAC algorithm. In: Baldoni, Matteo, Bandini, Stefania (eds.) AIxIA 2020. LNCS (LNAI), vol. 12414, pp. 301\u2013317. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-77091-4_19"},{"key":"33_CR13","unstructured":"Wallace, R.J.: Experimental analysis of restricted forms of SAC based reasoning for constraint satisfaction problems: preliminary results. In: Maratea, M., Vallati, M. (eds.) Twenty-ninth RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion - RCRA 2022 (2022)"}],"container-title":["Communications in Computer and Information Science","Artificial Intelligence and Cognitive Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-26438-2_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T21:16:54Z","timestamp":1728940614000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-26438-2_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031264375","9783031264382"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-26438-2_33","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 February 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AICS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Irish Conference on Artificial Intelligence and Cognitive Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munster","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ireland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 December 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aics2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/aics2022.mtu.ie\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"102","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}