TY - JOUR

T1 - An optimal coarse-grained arc consistency algorithm

AU - Bessière, Christian

AU - Régin, Jean Charles

AU - Yap, Roland H.C.

AU - Zhang, Yuanlin

N1 - Funding Information:
✩ Preliminary versions of this paper appeared in [C. Bessière, J. Régin, in: Proc. IJCAI-01, Seattle, WA, 2001, pp. 309–315 [1]; Y. Zhang, R. Yap, in: Proc. IJCAI-01, Seattle, WA, 2001, pp. 316–321 [2]]. ✩✩ During this work, Christian Bessière was supported by ILOG under a research collaboration contract ILOG/CNRS/University of Montpelier II, Yuanlin Zhang by the Science Foundation Ireland under Grant 00/PI.1/C075, at the Cork Constraint Computation Centre, Computer Science Department, University College Cork, and Roland Yap and Yuanlin Zhang by the Academic Research Fund, National University of Singapore. * Corresponding author. E-mail addresses: bessiere@lirmm.fr (C. Bessière), regin@ilog.fr (J.-C. Régin), ryap@comp.nus.edu.sg (R.H.C. Yap), yzhang@cs.ttu.edu (Y. Zhang).

PY - 2005/7

Y1 - 2005/7

N2 - 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.

AB - 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.

KW - Arc consistency

KW - Constraint networks

KW - Constraint programming systems

KW - Non-binary constraints

KW - Path consistency

UR - http://www.scopus.com/inward/record.url?scp=18944390206&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2005.02.004

DO - 10.1016/j.artint.2005.02.004

M3 - Article

AN - SCOPUS:18944390206

VL - 165

SP - 165

EP - 185

JO - Artificial Intelligence

JF - Artificial Intelligence

SN - 0004-3702

IS - 2

ER -