Skip to Main content Skip to Navigation
Conference papers

The ROOTS Constraint

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Christian Bessiere <>
Submitted on : Thursday, March 8, 2007 - 10:46:12 AM
Last modification on : Monday, January 11, 2021 - 5:24:15 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 9:59:43 PM




Christian Bessière, 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⟩



Record views


Files downloads