Partial (Neighbourhood) Singleton Arc Consistency for Constraint Satisfaction Problems

• Autorzy: Wallace Richard J.

Identyfikatory

DOI

10.3233/FI-2020-1944

• Języki publikacji: EN

Abstrakty

EN

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. Such consistencies, despite their partial character, are still well-characterized in that algorithms have unique fixpoints. Heuristic strategies for choosing an effective subset of variables are described and tested, the best being choice by highest degree and a more complex strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as the corresponding full version of the algorithm in terms of values discarded or problems proven unsatisfiable, while significantly reducing the effort required to achieve this.

Słowa kluczowe

EN

constraint satisfaction; neighborhoods; constraint algorithms; search algorithms; algorithms; tabu search algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 174, nr 3/4
• Strony: 311--344
• Opis fizyczny: Bibliogr. 19 poz., rys., tab., wykr.

Twórcy

autor

Wallace Richard J.

• Insight Centre for Data Analytics Department of Computer Science, University College Cork, Cork, Ireland

Bibliografia

• [1] Debruyne R, Bessière C. Some practicable filtering techniques for the constraint satisfaction problem. In: Fifteenth International Joint Conference on Artifcial Intelligence - IJCAI’97. Vol. 1. Morgan Kaufmann, 1997 pp. 412-417.
• [2] Wallace RJ. SAC and neighbourhood SAC. AI Communications, 2015. 28:345-364. doi:10.3233/AIC-140635.
• [3] Wallace RJ. Neighbourhood SAC: Extensions and new algorithms. AI Communications, 2016. 29:249-268. doi:10.3233/AIC-150696.
• [4] Berlandier P. Improving domain filtering using restricted path consistency. In: Conference on Artificial Intelligence for Applications - CAIA-95. 1995 pp. 32-37.
• [5] Wallace RJ. Preprocessing versus search processing for constraint satisfaction problems. In: Bistarelli S, Formisano A, Maratea M (eds.), 23rd RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion. 2016. URL http://ceur-ws.org/Vol-1745/paper7.pdf.
• [6] Wallace RJ. Partial (neighbourhood) singleton arc consistency for constraint satisfaction problems. In: Brawner K, Rus V (eds.), Thirty-First International Florida Artificial Intelligence Research Society Conference - FLAIRS-31. AAAI Press, 2018 pp. 140-145. URL wallaceflairs31ms36.pdf.
• [7] Wallace RJ. 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. AAAI Press, 2015 pp. 91-96.
• [8] Bessière C, Debruyne R. Optimal and suboptimal singleton arc consistency algorithms. In: Nineteenth International Joint Conference on Artificial Intelligence - IJCAI’05. 2005 pp. 54-59.
• [9] Lecoutre C, Cardon S. A greedy approach to establish singleton arc consistency. In: Fourteenth International Joint Conference on Artificial Intelligence - IJCAI’05. Professional Book Center, 2005 pp. 199-204.
• [10] Wallace RJ, Grimes D. Experimental studies of variable selection strategies based on constraint weights. Journal of Algorithms: Algorithms in Cognition, Informatics and Logic, 2008. 63(1-3):114-129. URL https://doi.org/10.1016/j.jalgor.2008.02.009.
• [11] Boussemart F, Hemery F, Lecoutre C, Sais L. Boosting systematic search by weighting constraints. In: Proc. Sixteenth European Conference on Artificial Intelligence-ECAI’04. IOS, 2004 pp. 146-150.
• [12] Grimes D, Wallace RJ. Learning to identify global bottlenecks in constraint satisfaction search. In: Proc. Twentieth International FLAIRS Conference. AAAI Press, 2007 pp. 592-598.
• [13] Lombardi M, Milano M, Roli A, Zanarini A. Deriving information from sampling and diving. Fundamenta Informaticae, 2011. 107:267-287.
• [14] Wallace RJ. Complexity analysis vs. engineering design in CSP algorithms: Contravening conventional wisdom again. In: Bistarelli S, Formisano A, Maratea M (eds.), 23rd RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion. 2016.
• [15] Wallace RJ. Neighbourhood SAC for constraint satisfaction problems with non-binary constraints. In: Markov Z, Russell I (eds.), Twenty-Ninth International Florida Artificial Intelligence Research Society Conference - FLAIRS-29. AAAI Press, 2016 pp. 162-165. URL wallace-flairs29.pdf.
• [16] Sakkout HE, Wallace MG, Richards EB. An instance of adaptive constraint propagation. In: Freuder EC (ed.), Principles and Practice of Constraint Programming - CP’96. LNCS. No. 1118, pp. 164-178. Springer, 1996. doi:10.1007/3-540-61551-2_73.
• [17] Mehta D, van Dongen MRC. Probabilistic consistency boosts MAC and SAC. In: Twentieth International Joint Conference on Artificial Intelligence - IJCAI 2007, pp. 143-148. IJCAI, 2007.
• [18] Stergiou K. Heuristics for dynamically adapting propagation. In: M Ghallab NF C D Spyropoulos, Avouris N (eds.), Eighteenth European Conference on Artificial Intelligence - ECAI. 2008 pp. 485-489. doi:10.3233/978-1-58603-891-5-485.
• [19] Balafrej A, Bessière C, Bouyakhf E, Trombettoni G. Adaptive singleton-based consistencies. In: Twenty-Eighth AAAI Conference on Artificial Intelligence - AAAI 2014. AAAI, 2014 pp. 2601-2607. URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-01067213.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).