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. The table constraint is a general constraint which can define an arbitrary constraint extensionally, either as a set of solutions or a set of non-solutions, thus is able to represent any finite domain constraint. Table constraint can also be converted to and solved on other representations, such as multi-valued decision diagrams (MDD), automaton and grammar.

In this thesis, we focus on the design, optimization and analysis of propagation algorithms for the related non-binary constraints using different representations. Some of these constraints, e.g. regular and grammar constraints, can also be thought as table constraints. We first propose a generalized arc consistency (GAC) algorithm for the regular constraint defined on non-deterministic finite automaton (NFA), called nfac. The nfac algorithm can also propagate the constraint represented by deterministic finite automaton (DFA) or MDD. We investigate the effect of different representations focusing on the space-time tradeoffs. We also extend nfac to grammarc for grammar constraint expressed on context free grammar.

Second, we revise the state-of-the-art GAC algorithms, STR, for table constraint, so that they can work on compressed representations.
The table is compressed using a Cartesian product representation, which we call c-tuple. We extend the STR2 and STR3 algorithms to work with c-tuples. Our experiments show that compression can be significant, the more the tables are compressible, the faster are the c-tuple algorithms.

Higher-order consistencies, such as full pairwise consistency (FPWC), are stronger than GAC and have the potential of stronger search space reduction. However, higher-order consistencies are usually much more costly than GAC, and thus not many practical propagation algorithms have been designed or implemented. We instead propose to transform one CSP into another "equivalent" one, so that FPWC can be enforced on the original CSP through GAC on the transformed one. Experiments show that our encoding with more compact representation can outperform the specialised eSTR algorithm and the k-interleaved encoding. We again demonstrate that both time and space efficiency can be gained from a smaller representation.