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

DOI10.1007/s10601-009-9087-yzbMath1204.68188OpenAlexW2003516442MaRDI 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 constraintad hoc constraintgeneralized arc consistencymulti-valued decision diagramnegative constraintpositive constrainttable constraint

Mathematics Subject Classification ID

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

Related Items

Strong local consistency algorithms for table constraints ⋮ Theoretical insights and algorithmic tools for decision diagram-based optimization ⋮ Efficient operations between MDDs and constraints ⋮ Decision Diagrams for Discrete Optimization: A Survey of Recent Advances ⋮ STR2: optimized simple tabular reduction for table constraints ⋮ How efficient is a global constraint in practice? A fair experimental framework ⋮ Generating custom propagators for arbitrary constraints ⋮ Domain consistency with forbidden values ⋮ 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 ⋮ Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints ⋮ 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 ⋮ MDDs boost equation solving on discrete dynamical systems

Uses Software

• MiniSat
• SICStus

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints