Partial (neighbourhood) singleton arc consistency for constraint satisfaction problems
| dc.contributor.author | Wallace, Richard J. | |
| dc.date.accessioned | 2021-10-05T14:46:53Z | |
| dc.date.available | 2021-10-05T14:46:53Z | |
| dc.date.issued | 2018-05 | |
| dc.description.abstract | Algorithms based on singleton arc consistency (SAC) show considerable promise for improving backtrack search algorithms for constraint satisfaction problems (CSPs). The drawback is that even the most efficient of them is still comparatively expensive. Even when limited to preprocessing, they give overall improvement only when problems are quite difficult to solve with more typical procedures such as maintained arc consistency (MAC). The present work examines a form of partial SAC and neighbourhood SAC (NSAC) in which a subset of the variables in a CSP are chosen to be made SAC-consistent or neighbourhood-SAC-consistent. These consistencies are well-characterized in that algorithms have unique fixpoints and there are well-defined dominance relations. Heuristic strategies for choosing an effective subset of variables are described and tested, in particular a strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as full (N)SAC in terms of values discarded while significantly reducing the effort required. | en |
| dc.description.status | Peer reviewed | en |
| dc.description.version | Accepted Version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.citation | Wallace, Richard J. (2018) ‘Partial (Neighbourhood) Singleton Arc Consistency for Constraint Satisfaction Problems’, Proceedings of the Thirty-First International Florida Artificial Intelligence Research Society Conference, FLAIRS 2018, Melbourne, Florida, USA. 21-23 May, AAAI Press, pp. 140-145 | en |
| dc.identifier.endpage | 145 | en |
| dc.identifier.startpage | 140 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/12052 | |
| dc.language.iso | en | en |
| dc.publisher | AAAI Press | en |
| dc.relation.uri | https://aaai.org/ocs/index.php/FLAIRS/FLAIRS18/paper/view/17620 | |
| dc.rights | © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). | en |
| dc.subject | Singleton arc consistency (SAC) | en |
| dc.subject | Algorithms | en |
| dc.subject | Constraint satisfaction problems (CSPs) | en |
| dc.subject | SAC-based reasoning | en |
| dc.title | Partial (neighbourhood) singleton arc consistency for constraint satisfaction problems | en |
| dc.type | Conference item | en |
