An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints

DOI10.1007/s10601-009-9087-yzbMath1204.68188MaRDI QIDQ968351

Roland H. C. Yap, Kenil C. K. Cheng

Publication date: 5 May 2010

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-009-9087-y

zbMATH Keywords

global constraint; ad hoc constraint; generalized arc consistency; multi-valued decision diagram; negative constraint; positive constraint; table constraint

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Strong local consistency algorithms for table constraints, STR2: optimized simple tabular reduction for table constraints, Domain consistency with forbidden values, How efficient is a global constraint in practice? A fair experimental framework, Scheduling double round-robin tournaments with divisional play using constraint programming, MDDs are efficient modeling tools: an application to some statistical constraints, Computing AES related-key differential characteristics with constraint programming, From MDD to BDD and arc consistency, Compiling CP subproblems to MDDs and d-DNNFs, STR3: a path-optimal filtering algorithm for table constraints, Optimal and efficient filtering algorithms for table constraints, Improving the lower bound of simple tabular reduction, Theoretical insights and algorithmic tools for decision diagram-based optimization, Generating custom propagators for arbitrary constraints, Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints

Uses Software

• MiniSat
• SICStus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Applying ad-hoc global constraints with the case constraint to still-life
• Introducing global constraints in CHIP
• Partition search for non-binary constraint satisfaction
• An optimal coarse-grained arc consistency algorithm
• Generalized Arc Consistency for Positive Table Constraints
• Revisiting the Sequence Constraint
• Graph-Based Algorithms for Boolean Function Manipulation
• Improving the variable ordering of OBDDs is NP-complete
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Principles and Practice of Constraint Programming – CP 2004