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

DOI10.1007/S10601-009-9087-YzbMATH Open1204.68188OpenAlexW2003516442MaRDI QIDQ968351FDOQ968351

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

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

Recommendations

• From MDD to BDD and arc consistency
• Generalized Arc Consistency for Positive Table Constraints
• STR2: optimized simple tabular reduction for table constraints
• Efficient operations between MDDs and constraints
• Constructions and in-place operations for MDDs based constraints

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)

Cites Work

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

Cited In (21)

• STR3: a path-optimal filtering algorithm for table constraints
• Computing AES related-key differential characteristics with constraint programming
• Theoretical insights and algorithmic tools for decision diagram-based optimization
• From MDD to BDD and arc consistency
• Optimal and efficient filtering algorithms for table constraints
• Strong local consistency algorithms for table constraints
• MDDs boost equation solving on discrete dynamical systems
• STR2: optimized simple tabular reduction for table constraints
• Improving the lower bound of simple tabular reduction
• Constructions and in-place operations for MDDs based constraints
• How efficient is a global constraint in practice? A fair experimental framework
• Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
• MDD propagation for sequence constraints
• Generating custom propagators for arbitrary constraints
• MDDs are efficient modeling tools: an application to some statistical constraints
• Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
• Domain consistency with forbidden values
• Efficient operations between MDDs and constraints
• Generalized Arc Consistency for Positive Table Constraints
• Scheduling double round-robin tournaments with divisional play using constraint programming
• Compiling CP subproblems to MDDs and d-DNNFs

Uses Software

• MiniSat
• SICStus

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968351)