05586279

a

05586279 Zhou, Neng-Fa Encoding table constraints in CLP(FD) based on pair-wise AC. Hill, Patricia M. (ed.) et al., Logic programming. 25th international conference, ICLP 2009, Pasadena, CA, USA, July 14--17, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02845-8/pbk). Lecture Notes in Computer Science 5649, 402-416 (2009). 2009 Berlin: Springer EN

doi:10.1007/978-3-642-02846-5_33

Summary: We present an implementation of table constraints in CLP(FD). For binary constraints, the supports of each value are represented as a finite-domain variable, and action rules are used to propagate value exclusions. The bit-vector representation of finite domains facilitates constant-time removal of unsupported values. For n-ary constraints, we propose pair-wise arc consistency (AC), which ensures that each value has a support in the domain of every related variable. Pair-wise AC does not require introducing new problem variables as done in binarization methods and allows for compact representation of constraints. Nevertheless, pair-wise AC is weaker than general arc consistency (GAC) in terms of pruning power and requires a final check when a constraint becomes ground. To remedy this weakness, we propose adopting early checks when constraints are sufficiently instantiated. Our experimentation shows that pair-wise AC with early checking is as effective as GAC for positive constraints.