Abstract
Constraint check plays a central role in establishing generalized arc consistency which is widely used to solve constraint satisfaction problems. In this paper, we propose a new generalized arc consistency algorithm, called GTR, which ensures that the tuples that have been checked to be allowed by a constraint will never be checked again. For each constraint, GTR maintains a dynamic list of the tuples that were checked to be allowed by this constraint and check their validities to identify some values with supports. It is equipped with a mechanism avoiding redundant validity checks. The basic GAC3 algorithm is employed to find a support for the rest values and to add new tuples to the dynamic list. The experiments show that maintaining GTR during search saves a number of constraint checks. It also brings some improvements over cpu time while solving some CSPs with tight constraints.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
The two instances are downloaded from http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html.
References
Bessière C (1994) Arc-consistency and arc-consistency again. Artif Intell 65:179–190
Bessière C, Fargier H, Lecoutre C (2013) Global inverse consistency for interactive constraint satisfaction Proceedings of CP’13, pp 159–174
Bessière C, Freuder EC, Régin JC (1999) Using constraint metaknowledge to reduce arc consistency computation. Artif Intell 107:125–148
Bessière C, Régin JC (1997) Arc consistency for general constraint networks: preliminary results Proceedings of IJCAI’97, pp 398–404
Bessière C, Régin JC, Yap R, Zhang Y (2005) An optimal coarse-grained arc consistency algorithm. Artif Intell 165:165–185
Boussemart F, Hemery F, Lecoutre C, Sais L (2004) Boosting systematic search by weighting constraints Proceedings of ECAI’04, pp 146–150
Gomes C, Selman B, Kautz H (1998) Boosting combinatorial search through randomization Proceedings of AAAI’98, pp 431–437
Lecoutre C (2011) STR2: optimized simple tabular reduction for table constraints. Constraints 16:341–371
Lecoutre C, Boussemart F, Hemery F (2003) Exploiting multidirectionality in coarsegrained arc consistency algorithms Proceedings of CP’03, pp 480–494
Lecoutre C, Hemery F (2007) A study of residual supports in arc consistency Proceedings of IJCAI’07, pp 125–130
Lecoutre C, Likitvivatanavong C, Shannon S, Yap R, Zhang Y (2008) Maintaining arc consistency with multiple residues. Constraint Program Lett 2:3–19
Li H (2017) Narrowing support searching range in maintaining arc consistency for solving constraint satisfaction problems. IEEE access. doi:10.1109/ACCESS.2017.2690672
Li H, Liang Y, Guo J, Li Z (2013) Making simple tabular reduction works on negative table constraints Proceedings of AAAI’13, pp 1629–1630
Likitvivatanavong C, Zhang Y, Bowen J, Freuder EC (2004) Arc consistency in MAC a new perspective Proceedings of CPAI’04 workshop held with CP’04, pp 93–107
Likitvivatanavong C, Zhang Y, Shannon C, Bowen J, Freuder EC (2007) Arc consistency during search Proceedings of IJCAI’07, pp 137–142
Mackworth AK (1977) Consistency in networks of relations. Artif Intell 8:99–118
Mohr R, Henderson TC (1986) Arc and path consistency revisited. Artif Intell 28:225–233
Sabin D, Freuder EC (1994) Contradicting conventional wisdom in constraint satisfaction Proceedings of ECAI’94, pp 125–129
Ullmann JR (2007) Partition search for non-binary constraint satisfaction. Inf Sci 177:3639–3678
van Dongen MRC (2004) Saving support-checks does not always save time. Artif Intell Rev 21:317–334
Wang R, Xia W, Yap R, Li Z (2016) Optimizing simple table reduction with bitwise representation Proceedings of IJCAI’16, pp 787–793
Walsh T (1999) Search in a small world Proceedings of IJCAI’99, pp 1172–1177
Acknowledgments
This work was supported by the Fundamental Research Funds for the Central Universities (NO. 2412016KJ034), the Education Department of Jilin Province (Project NO. JJKH20170911KJ) and Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University (NO.93K172017K06).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interests
The authors declare that they have no conflicts of interest.
Rights and permissions
About this article
Cite this article
Li, H., Li, R. & Yin, M. Saving constraint checks in maintaining coarse-grained generalized arc consistency. Neural Comput & Applic 31 (Suppl 1), 499–508 (2019). https://doi.org/10.1007/s00521-017-3015-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00521-017-3015-7