Explaining the effects of preprocessing on constraint satisfaction search
| dc.contributor.author | Wallace, Richard J. | en |
| dc.date.accessioned | 2023-06-12T12:17:42Z | |
| dc.date.available | 2023-06-12T12:17:42Z | |
| dc.date.issued | 2023-02-23 | en |
| dc.description.abstract | 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 “problem reduction”, 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. | en |
| dc.description.status | Peer reviewed | en |
| dc.description.version | Published Version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.citation | Wallace, R.J. (2023) ‘Explaining the effects of preprocessing on constraint satisfaction search’, in L. Longo and R. O’Reilly (eds) Irish Conference on Artificial Intelligence and Cognitive Science, AICS 2022, Artificial Intelligence and Cognitive Science. CCIS,volume 1662, Cham: Springer Nature Switzerland, pp. 423–436.https://doi.org/10.1007/978-3-031-26438-2_33. | en |
| dc.identifier.doi | 10.1007/978-3-031-26438-2_33 | en |
| dc.identifier.endpage | 436 | en |
| dc.identifier.isbn | 9783031264375 | en |
| dc.identifier.isbn | 9783031264382 | en |
| dc.identifier.issn | 1865-0929 | en |
| dc.identifier.issn | 1865-0937 | en |
| dc.identifier.journaltitle | Communications in Computer and Information Science | en |
| dc.identifier.startpage | 423 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/14556 | |
| dc.identifier.volume | 1662 | en |
| dc.language.iso | en | en |
| dc.publisher | Springer | en |
| dc.relation.ispartof | Communications in Computer and Information Science | en |
| dc.relation.ispartof | Artificial Intelligence and Cognitive Science | en |
| dc.relation.ispartof | 30th Irish Conference, AICS 2022 | en |
| dc.rights | ©The Author(s) 2023. Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. | en |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | en |
| dc.subject | Constraint satisfaction | en |
| dc.subject | Preprocessing algorithm | en |
| dc.subject | Arc consistency | en |
| dc.subject | Neighbourhood singleton arc consistency | en |
| dc.title | Explaining the effects of preprocessing on constraint satisfaction search | en |
| dc.type | Article (peer-reviewed) | en |
| dc.type | book-chapter | en |
| dc.type | Conference item | en |
