Designing and Optimizing Representations for Non-Binary Constraints

Abstract

Global constraint plays a central role in constraint programming due to its strong modelling and efficient propagation. In this thesis, we focus on the design, optimization and analysis of propagation algorithms for non-binary constraints using different representations. We fist propose a GAC algorithm, nfac, for the regular constraint defined on NFA. Nfac can also propagate the constraint represented by DFA or MDD. We investigate the space-time tradeoffs of different representations. We also extend nfac to grammar constraint. Then we revise the state-of-the-art GAC algorithms, STR2 and STR3, for table constraint, so that they can work on compressed representation, c-tuples. Higher-order consistencies are stronger than GAC and have stronger search space reduction, but are more costly to enforce. Thus, only a few practical higher-order consistency algorithms have been designed. We propose to transform one CSP into another, so that higher-order consistencies can be enforced through GAC on the transformed one.