2.1.3. Filtering view

Once we know that a constraint for which not all variables are fixed yet is potentially feasible, the next question is to identify variable-value pairs of the form $\left(\mathrm{\pi £\pi \pi },\mathrm{\pi £\pi \pi }\right)$ such that, if value $\mathrm{\pi £\pi \pi }$ is assigned to variable $\mathrm{\pi £\pi \pi }$, the constraint has no solution. Since removing such values reduces a priori the search space, filtering is strongly supported by the implicit motto of constraint programming that the more you prune the better. Assuming that you already have a necessary and sufficient condition that can be evaluated in polynomial time for checking whether a constraint has at least one solution or not, you can directly reuse it for checking whether a value can be assigned or not to a variable. Since the number of variable-value pairs to check may be quadratic with respect to the total number of variables and values one usually prefers developing a dedicated filtering algorithm that is less costly than checking the feasibility condition on each variable-value pair.

For the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint a first filtering algorithmΒ [Regin94] is based on a characterisation of the edges of the variable-value graph that belong to a maximum matching but not to all. A matching on a graph is a set of edges of the graph such that no two edges have a vertex in common; it is maximum if its number of edges is maximum. We first introduce a digraph ${\stackrel{\beta }{G}}_{M}$ that is associated with a matching $M$ that matches all variables of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. The vertices of ${\stackrel{\beta }{G}}_{M}$ are defined as the variables and the values that can be assigned to the variables of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. To each value $\mathrm{\pi £\pi \pi }$ that can be assigned to a variable $\mathrm{\pi £\pi \pi }$ corresponds an arc of ${\stackrel{\beta }{G}}_{M}$ from $\mathrm{\pi £\pi \pi }$ to $\mathrm{\pi £\pi \pi }$. Finally, if value $\mathrm{\pi £\pi \pi }$ is matched to variable $\mathrm{\pi £\pi \pi }$ in the matching $M$ we add the reverse arc from $\mathrm{\pi £\pi \pi }$ to $\mathrm{\pi £\pi \pi }$ to the arcs of ${\stackrel{\beta }{G}}_{M}$. Now a variable $\mathrm{\pi £\pi \pi }$ can be assigned a value $\mathrm{\pi £\pi \pi }$ if and only if $\mathrm{\pi £\pi \pi }$ and $\mathrm{\pi £\pi \pi }$ belong to the same strongly connected component of ${\stackrel{\beta }{G}}_{M}$ or if there is a path consisting of distinct vertices and arcs of ${\stackrel{\beta }{G}}_{M}$ that start with $\left(\mathrm{\pi £\pi \pi },\mathrm{\pi £\pi \pi }\right)$ and ends up in an unmatched value with respect to matching $M$, seeΒ [Thiel04].

Another filtering algorithm for $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ based on Hall intervals just focuses on adjusting the minimum and maximum values of the variables. Given a set of domain variables, a Hall interval is an interval of values $\left[\mathrm{\pi \pi \pi €},\mathrm{\pi ’\pi }\right]$ denoted by ${\mathrm{\beta }}_{\left[\mathrm{\pi \pi \pi €},\mathrm{\pi ’\pi }\right]}$ such that there are $\mathrm{\pi ’\pi }-\mathrm{\pi \pi \pi €}+1$ variables whose domains are contained in ${\mathrm{\beta }}_{\left[\mathrm{\pi \pi \pi €},\mathrm{\pi ’\pi }\right]}$. A minimal Hall interval ${\mathrm{\beta }}_{\left[\mathrm{\pi \pi \pi €},\mathrm{\pi ’\pi }\right]}$ is a Hall interval that does not contain any Hall interval ${\mathrm{\beta }}_{\left[{\mathrm{\pi \pi \pi €}}^{\text{'}},{\mathrm{\pi ’\pi }}^{\text{'}}\right]}$ such that either $\mathrm{\pi \pi \pi €}={\mathrm{\pi \pi \pi €}}^{\text{'}}$ or $\mathrm{\pi ’\pi }={\mathrm{\pi ’\pi }}^{\text{'}}$. Given a Hall interval $\mathrm{\beta }$ and a variable $V$ whose domain is not included in $\mathrm{\beta }$ but intersects $\mathrm{\beta }$, the idea is to adjust the minimum (respectively maximum) value of variable $V$ to the smallest (respectively largest) value that does not belong to $\mathrm{\beta }$. FigureΒ 2.1.2 illustrates this idea on the constraint $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\beta ©{V}_{1},{V}_{2},{V}_{3},{V}_{4},{V}_{5},{V}_{6},{V}_{7},{V}_{8},{V}_{9}\beta ͺ\right)$ with ${V}_{1}\beta \left[1,2\right]$, ${V}_{2}\beta \left[1,2\right]$, ${V}_{3}\beta \left[2,5\right]$, ${V}_{4}\beta \left[4,5\right]$, ${V}_{5}\beta \left[5,6\right]$, ${V}_{6}\beta \left[4,6\right]$, ${V}_{7}\beta \left[1,9\right]$, ${V}_{8}\beta \left[8,9\right]$, ${V}_{9}\beta \left[8,9\right]$.

• PartΒ (A) of FigureΒ 2.1.2 shows in light blue, in light pink and in light yellow the three minimal Hall intervals associated with the initial domains of variables ${V}_{1},{V}_{2},\beta ―,{V}_{9}$.

• ${\mathrm{\beta }}_{\left[1,2\right]}$ corresponds to interval $\left[1,2\right]$, which contains the domains of ${V}_{1}$ and ${V}_{2}$.

• ${\mathrm{\beta }}_{\left[4,6\right]}$ corresponds to interval $\left[4,6\right]$, which contains the domains of ${V}_{4}$, ${V}_{5}$ and ${V}_{6}$.

• ${\mathrm{\beta }}_{\left[8,9\right]}$ corresponds to interval $\left[8,9\right]$, which contains the domains of ${V}_{8}$ and ${V}_{9}$.

• PartΒ (B) of FigureΒ 2.1.2 shows the first propagation step with respect to the Hall intervals ${\mathrm{\beta }}_{\left[1,2\right]}$, ${\mathrm{\beta }}_{\left[4,6\right]}$ and ${\mathrm{\beta }}_{\left[8,9\right]}$. First note that variables ${V}_{3}$ and ${V}_{7}$ are the only variables whose domain is not included in a Hall interval. Consequently ${V}_{3}$ and ${V}_{7}$ are candidates for adjusting their minimum or maximum domain values.

• Since the minimum value of ${V}_{3}$, that is i.e. value 2, belongs to the Hall interval ${\mathrm{\beta }}_{\left[1,2\right]}$ we adjust the minimum of ${V}_{3}$ to the smallest value that does not yet belong to any Hall interval, i.e. value 3.

• Since the maximum value of ${V}_{3}$, that is i.e. value 5, belongs to the Hall interval ${\mathrm{\beta }}_{\left[4,6\right]}$ we adjust the maximum value of ${V}_{3}$ to the largest value that does not yet belong to any Hall interval, i.e. value 3.

• Since the minimum value of ${V}_{7}$, that is i.e. value 1, belongs to the Hall interval ${\mathrm{\beta }}_{\left[1,2\right]}$ we adjust the minimum of ${V}_{7}$ to the smallest value that does not yet belong to any Hall interval, i.e. value 3.

• Since the maximum value of ${V}_{7}$, that is i.e. value 9, belongs to the Hall interval ${\mathrm{\beta }}_{\left[8,9\right]}$ we adjust the maximum of ${V}_{7}$ to the largest value that does not yet belong to any Hall interval, that is i.e. value 7.

• PartΒ (C) of FigureΒ 2.1.2 shows the second propagation step with respect to the new Hall interval ${\mathrm{\beta }}_{\left[3,3\right]}$. Now ${V}_{7}$ is the only variable whose domain is not included in a Hall interval so it is a candidate for adjusting its minimum or maximum domain value.

• Since the minimum value of ${V}_{7}$, i.e. value 3, belongs to the new Hall interval ${\mathrm{\beta }}_{\left[3,3\right]}$ we adjust the minimum of ${V}_{7}$ to the smallest value that does not yet belong to any Hall interval, i.e. value 7.

• Finally, partΒ (D) of FigureΒ 2.1.2 shows all the minimal Hall intervals after reaching the fix point of the filtering, where ${\mathrm{\beta }}_{\left[7,7\right]}$ is a new minimal Hall interval.