Decomposition of the NValue Constraint

We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate with the same time complexity but with a much greater space complexity. This suggests that the benefit of a global propagator may often not be in saving time but in saving space. Our other theoretical contribution is to show for the first time that range consistency can be enforced on NVALUE with the same worst-case time complexity as bound consistency. Finally, the decompositions we study are readily encoded as linear inequalities. We are therefore able to use them in integer linear programs.

• Publication year

  2009

• Venue

  International Conference on Principles and Practice of Constraint Programming

• Publication date

  2009-09-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-15396-9_12arXiv 0909.3273
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Decompositions of All Different, Global Cardinality and Related Constraints

  2009influential reference
• Circuit Complexity and Decompositions of Global Constraints

  2009influential reference
• The Parameterized Complexity of Global Constraints

  2008cited by this paper
• SLIDE: A Useful Special Case of the CARDPATH Constraint

  2008influential reference
• Encodings of the Sequence Constraint

  2007cited by this paper
• The Complexity of Reasoning with Global Constraints

  2007cited by this paper
• Decomposing Global Grammar Constraints

  2007cited by this paper
• Propagation = Lazy Clause Generation

  2007cited by this paper
• On global warming: Flow-based soft global constraints

  2006cited by this paper
• Revisiting the Sequence Constraint

  2006cited by this paper
• The ROOTS Constraint

  2006influential reference
• The Range Constraint: Algorithms and Implementation

  2006cited by this paper
• Global Grammar Constraints

  2006cited by this paper
• Filtering Algorithms for the NValue Constraint

  2005influential reference
• Reformulation of Global Constraints Based on Constraints Checkers

  2005cited by this paper
• The Range and Roots Constraints: Specifying Counting and Occurrence Problems

  2005cited by this paper
• Filtering Algorithms for the Same Constraint

  2004cited by this paper
• The Complexity of Global Constraints

  2004cited by this paper
• To Be or Not to Be ... a Global Constraint

  2003influential reference
• Values of Domination Numbers of the Queen's Graph

  2001cited by this paper
• Pruning for the Minimum Constraint Family and for the Number of Distinct Values Constraint Family

  2001cited by this paper
• The Difference All-Difference Makes

  1999cited by this paper
• Automatic Generation of Music Programs

  1999influential reference
• A Fast Algorithm for the Bound Consistency of alldiff Constraints

  1998cited by this paper
• Some Practicable Filtering Techniques for the Constraint Satisfaction Problem

  1997cited by this paper
• A Filtering Algorithm for Constraints of Difference in CSPs

  1994cited by this paper
• To be or Not to Be

  1957influential reference

• SAT vs CSP: a commentary

  2019cites this paper
• Functional description of sequence constraints and synthesis of combinatorial objects. (Description fonctionnelle de contraintes sur des séquences et synthèse d'objets combinatoires)

  2018cites this paper
• Reasoning about NP-complete Constraints

  2018cites this paper
• Education Awards

  2018cites this paper
• Constraint Programming Models for Conceptual Clustering: Application to an ERP Configuration Problem. (Modèles de programmation par contraintes pour le clustering conceptuel: application à un problème de configuration d'ERP)

  2018cites this paper
• Automatic Generation of Descriptions of Time-Series Constraints

  2017cites this paper
• Analysis, synthesis and application of automaton-based constraint descriptions

  2017cites this paper
• Hybrid methodologies for symmetric and asymmetric vehicle routing problems

  2016cites this paper
• Systematic Derivation of Bounds and Glue Constraints for Time-Series Constraints

  2016cites this paper
• Integration of AI and OR Techniques in Constraint Programming: 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Proceedings

  2015cites this paper
• Structural decompositions for problems with global constraints

  2015cites this paper
• New filtering for AtMostNValue and its weighted variant: A Lagrangian approach

  2015influential citation
• An application of constraint solving for home health care

  2015cites this paper
• Fusion ensembliste de donn´ees pour la surveillance des personnes d´ependantes en habitat intelligent

  2015cites this paper
• Global Conference on Artificial Intelligence Implied Constraints for Automaton Constraints

  2015cites this paper
• Autour de la d´ecomposition des contraintes non-binaires en contraintes binaires ´equivalentes ∗

  2015cites this paper
• Generation of Implied Constraints for Automaton-Induced Decompositions

  2013cites this paper
• Hybrid tractability of constraint satisfaction problems with global constraints

  2013cites this paper
• Lifting Structural Tractability to CSP with Global Constraints

  2013cites this paper
• Tractable Combinations of Global Constraints

  2013cites this paper
• Exploiting Constraints

  2011cites this paper
• Consistency of constraint networks induced by automaton-based constraint specifications

  2011cites this paper