An optimal coarse-grained arc consistency algorithm. (English) Zbl 1132.68691

Bessière, Christian; Régin, Jean-Charles; Yap, Roland H. C.; Zhang, Yuanlin

Artif. Intell. 165, No. 2, 165-185 (2005).

Summary: The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3.1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3.1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints.

MSC:

68T20

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

Keywords:

arc consistency; constraint programming systems; constraint networks; path consistency; non-binary constraints

Software:

Choco

References:

[1]	Bessière, C.; Régin, J., Refining the basic constraint propagation algorithm, (Proc. IJCAI-01, Seattle, WA (2001)), 309-315
[2]	Zhang, Y.; Yap, R., Making AC-3 an optimal algorithm, (Proc. IJCAI-01, Seattle, WA (2001)), 316-321
[3]	Mackworth, A., Consistency in networks of relations, Artificial Intelligence, 8, 99-118 (1977) · Zbl 0341.68061
[4]	McGregor, J., Relational consistency algorithms and their application in finding subgraph and graph isomorphism, Inform. Sci., 19, 229-250 (1979) · Zbl 0442.68065
[5]	Mohr, R.; Henderson, T., Arc and path consistency revisited, Artificial Intelligence, 28, 225-233 (1986)
[6]	Bessière, C.; Freuder, E. C.; Régin, J. C., Using inference to reduce arc consistency computation, (Proc. IJCAI-95, Montréal, Canada (1995)), 592-598
[7]	Bessière, C.; Freuder, E.; Régin, J., Using constraint metaknowledge to reduce arc consistency computation, Artificial Intelligence, 107, 125-148 (1999) · Zbl 0911.68192
[8]	Mackworth, A.; Freuder, E., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, 25, 65-74 (1985)
[9]	Chmeiss, A.; Jégou, P., Efficient path-consistency propagation, Internat. J. Artificial Intelligence Tools, 7, 2, 121-142 (1998)
[10]	Wallace, R., Why AC-3 is almost always better than AC-4 for establishing arc consistency in CSPs, (Proc. IJCAI-93, Chambéry, France (1993)), 239-245
[11]	Bessière, C., Arc-consistency and arc-consistency again, Artificial Intelligence, 65, 179-190 (1994)
[12]	Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artificial Intelligence, 34, 1-38 (1988) · Zbl 0643.68156
[13]	Prosser, P., An empirical study of phase transition in binary constraint satisfaction problems, Artificial Intelligence, 81, 1-2, 81-109 (1996) · Zbl 07589958
[14]	Frost, D.; Bessière, C.; Dechter, R.; Régin, J., Random uniform CSP generators (1996)
[15]	Cabon, C.; de Givry, S.; Lobjois, L.; Schiex, T.; Warners, J., Radio link frequency assignment, Constraints, 4, 79-89 (1999) · Zbl 1020.94500
[16]	Gent, I.; MacIntyre, E.; Prosser, P.; Shaw, P.; Walsh, T., The constrainedness of arc consistency, (Proc. CP-97 Linz, Austria (1997)), 327-340
[17]	Sabin, D.; Freuder, E., Contradicting conventional wisdom in constraint satisfaction, (Proceedings of the Second Workshop on Principles and Practice of Constraint Programming, Rosario, Orcas Island, WA (1994)), 10-20
[18]	Singh, M., Path consistency revisited, Internat. J. Artificial Intelligence Tools, 6, 1-2, 127-141 (1996)
[19]	Mackworth, A., On reading sketch maps, (Proc. IJCAI-77, Cambridge, MA (1977)), 598-606
[21]	Laburthe, F., User’s manual, CHOCO (2000)
[22]	Perlin, M., Arc consistency for factorable relations, Artificial Intelligence, 53, 329-342 (1992) · Zbl 1193.68140
[23]	Gaschnig, J., Experimental case studies of backtrack vs waltz-type vs new algorithms for satisfying assignment problems, (Proc. CCSCSI-78 (1978)), 268-277
[24]	Lecoutre, C.; Boussemart, F.; Hemery, F., Exploiting multidirectionality in coarse-grained arc consistency algorithms, (Proc. CP-03, Kinsale, Ireland (2003)), 480-494
[25]	Wallace, R.; Freuder, E., Ordering heuristics for arc consistency algorithms, (Proceedings of the Ninth Canadian Conference on Artificial Intelligence, Vancouver, Canada (1992)), 163-169
[26]	Mohr, R.; Masini, G., Good old discrete relaxation, (Proc. ECAI-88, Munchen, FRG (1988)), 651-656
[27]	Bessière, C.; Régin, J., Arc consistency for general constraint networks: preliminary results, (Proc. IJCAI-97, Nagoya, Japan (1997)), 398-404
[28]	Van Hentenryck, P.; Deville, Y.; Teng, C., A generic arc-consistency algorithm and its specializations, Artificial Intelligence, 57, 291-321 (1992) · Zbl 0763.68059
[29]	Zhang, Y.; Yap, R., Arc consistency on n-ary monotonic and linear constraints, (Proc. CP-00, Singapore (2000)), 470-483 · Zbl 1044.68810