3.7.38. Bound-consistency

Denotes 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 𝚗𝚟𝚊𝚕𝚞𝚎 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 𝚔_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 constraint, bound-consistency is only achieved when we have two overlapping 𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 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 to ctr such that V=V ̲ and every other domain variable W of ctr is assigned to a value located in its range [W ̲,W ¯],

  • There exists at least one solution to ctr such that V=V ¯ and every other domain variable W of ctr is assigned to a value located in its range [W ̲,W ¯].

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 [W ̲,W ¯] 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 (V,v) such that V is a set variable of ctr and v an integer value, if vV ̲ then v belongs to the set assigned to V in all solutions to ctr and if vV ¯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.