The ROOTS Constraint - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2006

The ROOTS Constraint


A wide range of counting and occurrence constraints can be specified with just two global primitives: the Range constraint, which computes the range of values used by a sequence of variables, and the Roots constraint, which computes the variables mapping onto a set of values. We focus here on the Roots constraint. We show that propagating the Roots constraint completely is intractable. We therefore propose a decomposition which can be used to propagate the constraint in linear time. Interestingly, for all uses of the Roots constraint we have met, this decomposition does not destroy the global nature of the constraint as we still prune all possible values. In addition, even when the Roots constraint is intractable to propagate completely, we can enforce bound consistency in linear time simply by enforcing bound consistency on the decomposition. Finally, we show that specifying counting and occurrence constraints using Roots is effective and efficient in practice on two benchmark problems from CSPLib.
Fichier principal
Vignette du fichier
cp06-roots.pdf (165.97 Ko) Télécharger le fichier

Dates and versions

lirmm-00135537 , version 1 (08-03-2007)



Christian Bessiere, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh. The ROOTS Constraint. CP: Principles and Practice of Constraint Programming, Sep 2006, Nantes, France. pp.75-90, ⟨10.1007/11889205_8⟩. ⟨lirmm-00135537⟩
138 View
176 Download



Gmail Facebook X LinkedIn More