×

Theoretical analysis of singleton arc consistency and its extensions. (English) Zbl 1182.68217

Summary: Singleton arc consistency (SAC) is a consistency property that is simple to specify and is stronger than arc consistency. Algorithms have already been proposed to enforce SAC, but they have a high time complexity. In this paper, we give a lower bound to the worst-case time complexity of enforcing SAC on binary constraints. We discuss two interesting features of SAC. The first feature leads us to propose an algorithm for SAC that has optimal time complexity when restricted to binary constraints. The second feature leads us to extend SAC to a stronger level of local consistency that we call Bidirectional SAC (BiSAC). We also show the relationship between SAC and the propagation of disjunctive constraints.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

cc(FD)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Applegate, D.; Bixby, R.; Chvátal, V.; Cook, W., On the solution of traveling salesman problems, International congress of mathematicians, Documenta Mathematica journal der deutschen mathematiker-vereinigung, 645-656, (1998) · Zbl 0904.90165
[2] Barták, R.; Erben, R., A new algorithm for singleton arc consistency, ()
[3] Bennaceur, H.; Affane, M.S., Partition-k-AC: an efficient filtering technique combining domain partition and arc consistency, (), 560-564, Short paper · Zbl 1067.68614
[4] P. Berlandier, Improving domain filtering using restricted path consistency, in: Proceedings IEEE Conference on Artificial Intelligence and Applications (CAIA’95), 1995
[5] Bessiere, C., Arc-consistency and arc-consistency again, Artificial intelligence, 65, 179-190, (1994)
[6] C. Bessiere, R. Debruyne, Optimal and suboptimal singleton arc consistency algorithms, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI’05), Edinburgh, Scotland, 2005, pp. 54-59
[7] Bessiere, C.; Freuder, E.C.; Régin, J.C., Using constraint metaknowledge to reduce arc consistency computation, Artificial intelligence, 107, 125-148, (1999) · Zbl 0911.68192
[8] C. Bessiere, J.C. Régin, Arc consistency for general constraint networks: preliminary results, in: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI’97), Nagoya, Japan, 1997, pp. 398-404
[9] Bessiere, C.; Régin, J.C.; Yap, R.H.C.; Zhang, Y., An optimal coarse-grained arc consistency algorithm, Artificial intelligence, 165, 165-185, (2005) · Zbl 1132.68691
[10] Cooper, M.C., An optimal k-consistency algorithm, Artificial intelligence, 41, 89-95, (1989/90) · Zbl 0678.68058
[11] Debruyne, R.; Bessiere, C., From restricted path consistency to MAX-restricted path consistency, (), 312-326
[12] R. Debruyne, C. Bessiere, Some practicable filtering techniques for the constraint satisfaction problem, in: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI’97), Nagoya, Japan, 1997, pp. 412-417
[13] Debruyne, R.; Bessiere, C., Domain filtering consistencies, Journal of artificial intelligence research, 14, 205-230, (2001) · Zbl 0970.68125
[14] J.W. Freeman, Improvements to propositional satisfiability search algorithms, PhD thesis, University of Pennsylvania, Philadelphia PA, 1995
[15] Freuder, E.C., Synthesizing constraint expressions, Communications of the ACM, 21, 11, 958-966, (November 1978)
[16] Freuder, E.C., A sufficient condition for backtrack-free search, Journal of the ACM, 29, 1, 24-32, (January 1982)
[17] C. Lecoutre, S. Cardon, A greedy approach to establish singleton rc consistency, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI’05), Edinburgh, Scotland, 2005, pp. 199-204
[18] O. Lhomme, Consistency techniques for numeric csps, in: Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI’93), Chambéry, France, 1993, pp. 232-238
[19] Lhomme, O., Efficient filtering algorithm for disjunction of constraints, (), 904-908
[20] C.M. Li, Anbulagan, Heuristics based on unit propagation for satisfiability problems, in: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI’97), Nagoya, Japan, 1997, pp. 366-371
[21] Mackworth, A.K., Consistency in networks of relations, Artificial intelligence, 8, 99-118, (1977) · Zbl 0341.68061
[22] McGregor, J.J., Relational consistency algorithms and their application in finding subgraph and graph isomorphism, Information science, 19, 229-250, (1979) · Zbl 0442.68065
[23] Mohr, R.; Henderson, T.C., Arc and path consistency revisited, Artificial intelligence, 28, 225-233, (1986)
[24] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Information science, 7, 95-132, (1974) · Zbl 0284.68074
[25] Prosser, P.; Stergiou, K.; Walsh, T., Singleton consistencies, (), 353-368 · Zbl 1044.68790
[26] Van Hentenryck, P.; Saraswat, V.A.; Deville, Y., Design, implementation, and evaluation of the constraint language , Journal of logic programming, 37, 1-3, 139-164, (1998) · Zbl 0920.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.