Encoding Multi-Valued Decision Diagram Constraints as Binary Constraint Trees

No. 4: AAAI-22 Technical Tracks 4

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Technical Track on Constraint Satisfaction and Optimization

Ordered Multi-valued Decision Diagram (MDD) is a compact representation used to model various constraints, such as regular constraints and table constraints. It can be particularly useful for representing ad-hoc problem specific constraints. Many algorithms have been proposed to enforce Generalized Arc Consistency (GAC) on MDD constraints. In this paper, we introduce a new compact representation called Binary Constraint Tree (BCT). We propose tree binary encodings to transform any MDD constraint into a BCT constraint. We also present a specialized algorithm enforcing GAC on the BCT constraint resulting from a MDD constraint. Experimental results on a large set of benchmarks show that the BCT GAC algorithm can significantly outperform state-of-the-art MDD as well as table GAC algorithms.

10.1609/aaai.v36i4.20300