5.272. roots

Origin

[BessiereHebrardHnichKiziltanWalsh05IJCAI]

Constraint

roots​(S,​T,​VARIABLES)​

Argument(s)

S	svar
T	svar
VARIABLES	collection​(var−dvar)​

Restriction(s)

S≤|VARIABLES|

required​(VARIABLES,​var)​

Purpose

S is the set of indices of the variables in the collection VARIABLES taking their values in T; S=​{i | VARIABLES​[i]​.var∈T}​.

Example

( ​{2,​4,​5}​,​ ​{2,​3,​8}​,​ 〈1,​3,​1,​2,​3〉 )

The roots constraint holds since values 2 and 3 in T occur in the collection 〈1,​3,​1,​2,​3〉 only at positions S=​{2,​4,​5}​. The value 8∈T does not occur within the collection 〈1,​3,​1,​2,​3〉.

Usage

Bessière et al. showed [BessiereHebrardHnichKiziltanWalsh05IJCAI] that many counting and occurence constraints can be specified with two global primitives: roots and range. For instance, the count constraint can be decomposed into one roots constraint: count​(VAL,​VARS,​OP,​NVAR)​ iff roots​(S,​​{VAL}​,​VARS)​∧|S| OP NVAR.

roots does not count but collects the set of variables using particular values. It provides then a way of channeling. roots generalizes, for instance, the link_set_to_booleans constraint, link_set_to_booleans​(S,​BOOLEANS)​ iff roots​(S,​​{1}​,​BOOLEANS.bool)​, or may be used instead of the domain_constraint.

Algorithm

In [BessiereHebrardHnichKiziltanWalsh06CP], Bessière et al. shows that enforcing hybrid-consistency on roots is NP -hard. They consider the decomposition of roots into a network of ternary constraints: ∀i, i∈S⇒VARIABLES​[i]​.var∈T and VARIABLES​[i]​.var⇒T∧i∈S. Enforcing bound consistency on the decomposition achieves bound consistency on roots. Enforcing hybrid consistency on the decomposition achieves at least bound consistency on roots, until hybrid consistency in some special cases:

• dom​(VARIABLES​[i]​.var)​⊂T,​ ∀i∈S,

• dom​(VARIABLES​[i]​.var)​∩T=∅,​ ∀i∉S,

• VARIABLES are ground,

• T is ground.

Enforcing hybrid consistency on the decomposition can be done in O​(nd)​ with n=|VARIABLES| and d the maximum domain size of VARIABLES​[i]​.var and T.

See also

among, count, domain_constraint, link_set_to_booleans, global_cardinality, common.

Key words

characteristic of a constraint: disequality.

constraint arguments: constraint involving set variables.

constraint type: counting constraint, value constraint, decomposition.

filtering: hybrid-consistency.

Derived Collection(s)

col​(SETS−collection​(s−svar,​t−svar)​,​​[item​(s−S,​t−T)​]​)​

---

Arc input(s)

SETS VARIABLES

Arc generator

PRODUCT↦collection​(sets,​variables)​

Arc arity

2

Arc constraint(s)

in_set​(variables.key,​sets.s)​⇔in_set​(variables.var,​sets.t)​

Graph property(ies)

NARC=|VARIABLES|

---

Graph model

Figure 5.272.1. Initial and final graph of the roots constraint

(a)	(b)