Extending STR to a Higher-Order Consistency

Authors

  • Christophe Lecoutre Université d'Artois
  • Anastasia Paparrizou University of Western Macedonia
  • Kostas Stergiou University of Western Macedonia

DOI:

https://doi.org/10.1609/aaai.v27i1.8622

Keywords:

Constraint Propagation, Strong Local Consistencies, Table Constraints

Abstract

One of the most widely studied classes of constraints in constraint programming (CP) is that of table constraints. Numerousspecialized filtering algorithms, enforcing the wellknown property called generalized arc consistency (GAC),have been developed for such constraints. Among the most successful GAC algorithms for table constraints, we find variants of simple tabular reduction (STR), like STR2. In this paper,we propose an extension of STR-based algorithms that achieves full pairwise consistency (FPWC), a consistency stronger than GAC and max restricted pairwise consistency (maxRPWC). Our approach involves counting the number of occurrences of specific combinations of values in constraint intersections. Importantly, the worst-case time complexity of one call to the basic filtering procedure at the heart of our new algorithm is quite close to that of STR algorithms. Experiments demonstrate that our method can outperform STR2 in many classes of problems, being significantly faster in some cases. Also, it is clearly superior to maxRPWC+, an algorithm that has been recently proposed.

Downloads

Published

2013-06-30

How to Cite

Lecoutre, C., Paparrizou, A., & Stergiou, K. (2013). Extending STR to a Higher-Order Consistency. Proceedings of the AAAI Conference on Artificial Intelligence, 27(1), 576-582. https://doi.org/10.1609/aaai.v27i1.8622