The complexity of reasoning with global constraints

DOI10.1007/S10601-006-9007-3MaRDI QIDQ2454812zbMATH OpenOpenAlexFDO

Authors Emmanuel Hebrard, Brahim Hnich, Toby Walsh, 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 propagationGeneralized arc consistencyGlobal constraints

Mathematics Subject Classification ID

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

Abstract: Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domains of variables. With global (or non-binary) constraints, the cost of such propagation may be much greater than the quadratic cost for binary constraints. We therefore study the computational complexity of reasoning with global constraints. We first characterise a number of important questions related to constraint propagation. We show that such questions are intractable in general, and identify dependencies between the tractability and intractability of the different questions. We then demonstrate how the tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when constraints can be safely generalized, when decomposing constraints will reduce the amount of pruning, and when combining constraints is tractable.

Recommendations

• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2003
• Constraint satisfaction -- algorithms and complexity analysis
• Algorithms and Computation
• Generalizing Global Constraints Based on Network Flows

Cites work

• A comparison of structural CSP decomposition methods
• A Sufficient Condition for Backtrack-Free Search
• Approximated consistency for knapsack constraints
• Consistency and propagation with multiset constraints: a formal viewpoint
• Constraint satisfaction over connected row-convex constraints
• Cost-based arc consistency for global cardinality constraints
• Cost-based filtering for shorter path constraints
• Design, implementation, and evaluation of the constraint language cc(FD)
• Filtering Algorithms for the NValue Constraint
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2080298 (Why is no real title available?)
• scientific article; zbMATH DE number 2080320 (Why is no real title available?)
• scientific article; zbMATH DE number 2084707 (Why is no real title available?)
• scientific article; zbMATH DE number 2085269 (Why is no real title available?)
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Introducing global constraints in CHIP
• Network-based heuristics for constraint-satisfaction problems
• On the minimality and global consistency of row-convex constraint networks
• Optimization-oriented global constraints
• Principles and Practice of Constraint Programming – CP 2003
• The complexity of facets (and some facets of complexity)
• The Problem of Compatible Representatives
• Tree clustering for constraint networks

Cited in

(31)

• Modeling uncertainties with chance constraints
• The power of propagation: when GAC is enough
• How efficient is a global constraint in practice? A fair experimental framework
• Filtering algorithms for global chance constraints
• Dynamic global constraints in backtracking based environments
• On the reification of global constraints
• View-based propagation of decomposable constraints
• Structural decompositions for problems with global constraints
• The complexity of integer bound propagation
• The objective sum constraint
• Computing and restoring global inverse consistency in interactive constraint satisfaction
• Ad-hoc Global Constraints for Life
• The ROOTS Constraint
• Boosting set constraint propagation for network design
• STR2: optimized simple tabular reduction for table constraints
• Constraint propagation for ordering, abstraction, and aggregation relations
• scientific article; zbMATH DE number 2080298 (Why is no real title available?)
• When is it worthwhile to propagate a constraint? A probabilistic analysis of \textsc{AllDifferent}
• Self-decomposable global constraints
• Constraint-Level Advice for Shaving
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Principles and Practice of Constraint Programming – CP 2003
• Algorithms and Computation
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Recent Advances in Constraints
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004
• Implementing logical connectives in constraint programming
• Constraint reasoning
• Range and Roots: two common patterns for specifying and propagating counting and occurrence constraints

Describes a project that uses

Uses Software

• cc(FD)

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

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