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 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 of ctr:
There exists at least one solution for ctr such that and every other domain variable of ctr is assigned to a value located in its range ,
There exists at least one solution for ctr such that and every other domain variable of ctr is assigned to a value located in its range .
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 is replaced by the domain of the variable . 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 such that is a set variable of ctr and an integer value, if then belongs to the set assigned to in all solutions to ctr and if then belongs to the set assigned to in at least one solution and is excluded from this set in at least one solution.