The Expressive Power of Ad-Hoc Constraints for Modelling CSPs

Authors

  • Ruiwei Wang National University of Singapore
  • Roland H.C. Yap National University of Singapore

DOI:

https://doi.org/10.1609/aaai.v37i4.25526

Keywords:

CSO: Constraint Satisfaction, CSO: Constraint Programming, CSO: Other Foundations of Constraint Satisfaction & Optimization

Abstract

Ad-hoc constraints (also called generic constraints) are important for modelling Constraint Satisfaction Problems (CSPs). Many representations have been proposed to define ad-hoc constraints, such as tables, decision diagrams, binary constraint trees, automata and context-free grammars. However, prior works mainly focus on efficient Generalized Arc Consistency (GAC) propagators of ad-hoc constraints using the representations. In this paper, we ask a more fundamental question which bears on modelling constraints in a CSP as ad-hoc constraints, how the choice of constraints and operations affect tractability. Rather than ad-hoc constraints and their GAC propagators, our focus is on their expressive power in terms of succinctness (polysize) and cost of operations/queries (polytime). We use a large set of constraint families to investigate the expressive power of 14 existing ad-hoc constraints. We show a complete map of the succinctness of the ad-hoc constraints. We also present results on the tractability of applying various operations and queries on the ad-hoc constraints. Finally, we give case studies illustrating how our results can be useful for questions in the modelling of CSPs.

Downloads

Published

2023-06-26

How to Cite

Wang, R., & Yap, R. H. (2023). The Expressive Power of Ad-Hoc Constraints for Modelling CSPs. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 4104-4114. https://doi.org/10.1609/aaai.v37i4.25526

Issue

Section

AAAI Technical Track on Constraint Satisfaction and Optimization