The complexity of reasoning with global constraints

DOI10.1007/s10601-006-9007-3zbMath1124.68103arXiv0903.1139OpenAlexW1996050266MaRDI QIDQ2454812

Toby Walsh, Emmanuel Hebrard, Brahim Hnich, Christian Bessiere

Publication date: 22 October 2007

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0903.1139

zbMATH Keywords

Computational complexityConstraint propagationGlobal constraintsGeneralized arc consistency

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Modeling uncertainties with chance constraints ⋮ Structural decompositions for problems with global constraints ⋮ Range and Roots: two common patterns for specifying and propagating counting and occurrence constraints ⋮ Implementing logical connectives in constraint programming ⋮ The power of propagation: when GAC is enough ⋮ STR2: optimized simple tabular reduction for table constraints ⋮ Filtering algorithms for global chance constraints

Uses Software

• cc(FD)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of facets (and some facets of complexity)
• Network-based heuristics for constraint-satisfaction problems
• Tree clustering for constraint networks
• Constraint satisfaction over connected row-convex constraints
• A comparison of structural CSP decomposition methods
• Introducing global constraints in CHIP
• Optimization-oriented global constraints
• Cost-based arc consistency for global cardinality constraints
• A Sufficient Condition for Backtrack-Free Search
• The Problem of Compatible Representatives
• Design, implementation, and evaluation of the constraint language cc(FD)
• On the minimality and global consistency of row-convex constraint networks
• Filtering Algorithms for the NValue Constraint
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Principles and Practice of Constraint Programming – CP 2003
• Principles and Practice of Constraint Programming – CP 2003
• Principles and Practice of Constraint Programming – CP 2003
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: The complexity of reasoning with global constraints