### 3.7.36. Bound-consistency

Denotes the fact that, for a given constraint, there is a filtering algorithm or a reformulation in term of other constraints that ensures bound -consistency for its domain variables.In the context of the $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint, bound -consistency is only achieved if and only if, the minimum of the variable that denotes the number of distinct values is not constrained at all. In the context of the $𝚔_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint, bound -consistency is only achieved when we have two overlapping $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints, see [BessiereKatsirelosNarodytskaQuimperWalsh10] for more details. A filtering algorithm or a reformulation ensure bound -consistency for a given constraint ctr using distinct domain variables if and only if for every domain variable $V$ of ctr:

• There exists at least one solution for ctr such that $V=\underline{V}$ and every other domain variable $W$ of ctr is assigned to a value located in its range $\left[\underline{W},\overline{W}\right]$,

• There exists at least one solution for ctr such that $V=\overline{V}$ and every other domain variable $W$ of ctr is assigned to a value located in its range $\left[\underline{W},\overline{W}\right]$.

This consistency is called bound(Z) consistency in  [Bessiere06]. One of its interest is that it sometimes gives the opportunity to come up with a filtering algorithm that has a lower complexity than the algorithm that achieves arc -consistency. Discarding holes from the domain variables usually leads to graphs with a specific structure for which one can take advantage in order to derive more efficient graph algorithms. Filtering algorithms that achieve bound -consistency can also be used in a pre -processing phase before applying a more costly filtering algorithm that achieves arc -consistency.

Note that there is a second definition of bound -consistency, called bound(D) consistency in  [Bessiere06], where the range $\left[\underline{W},\overline{W}\right]$ is replaced by the domain of the variable $W$. However within the context of global constraints most filtering algorithms do not refer to this second definition.

Finally, within the context of constraints involving only set variables, bound -consistency is defined in the following way. A constraint ctr defined on distinct set variables is bound -consistent if and only if for every pair $\left(V,v\right)$ such that $V$ is a set variable of ctr and $v$ an integer value, if $v\in \underline{V}$ then $v$ belongs to the set assigned to $V$ in all solutions to ctr and if $v\in \overline{V}\setminus \underline{V}$ then $v$ belongs to the set assigned to $V$ in at least one solution and is excluded from this set in at least one solution.