### 3.7.105. Flow

A constraint for which there is a filtering algorithm based on an algorithm that finds a feasible flow in a graph. The graph is usually constructedSometimes it is also constructed from the reformulation of a global constraint in term of a conjunction of linear constraints. This is for instance the case for the $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ and the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ global constraints. from the variables of the constraint as well as from their potential values. The usual game is to come up with a flow model such that there exists a one to one correspondence between feasible flows in the flow model and solutions to the constraint, so that detecting arcs that cannot carry any flow in any feasible flow will lead removing some values from the domains of some variables. The next sections provide standard flow models for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, the , the , the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi ’}$, the $\mathrm{\pi \pi \pi \pi }$, and the constraints.

FigureΒ 3.7.28 presents flow models for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ and the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints. Blue arcs represent feasible flows respectively corresponding to the solutions $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\beta ©{x}_{1}=1,{x}_{2}=2,{x}_{3}=3,{x}_{4}=4,{x}_{5}=5\beta ͺ\right)$ and $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\left\{\mathbf{1},\mathbf{2},\mathbf{3},\mathbf{5}\right\},\beta ©{x}_{1}=1,{x}_{2}=2,{x}_{3}=3,{x}_{4}=3,{x}_{5}=4\beta ͺ\right)$, while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution. TablesΒ 3.7.27 andΒ 3.7.27 respectively provide the initial domains of the variables we assume for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ and $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints.

##### Table 3.7.27. Domains of the variables for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint of FigureΒ 3.7.28.
$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$
1$\left\{1,2\right\}$3$\left\{1,2,3\right\}$5$\left\{3,4,5,6\right\}$
2$\left\{1,2\right\}$4$\left\{2,3,4,5\right\}$
##### Table 3.7.27. Domains of the variables for the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint of FigureΒ 3.7.28. The lower and upper bounds of the set variable corresponding to the first argument of the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint are respectively equal to set of variables positions $\left\{1,2,3,5\right\}$, and $\left\{1,2,3,4,5\right\}$, where $\left\{\mathbf{1},\mathbf{2},\mathbf{3},4,\mathbf{5}\right\}$ is a shortcut for denoting both bounds.
$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$
1$\left\{1,2\right\}$3$\left\{1,2,3\right\}$5$\left\{3,4\right\}$
2$\left\{1,2\right\}$4$\left\{2,3\right\}$
• Within the context of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint the assignments ${x}_{3}=1$, ${x}_{3}=2$ and ${x}_{4}=2$ are forbidden since values 1 and 2 must already be assigned to variables ${x}_{1}$ and ${x}_{2}$. Finally the assignments ${x}_{4}=3$ and ${x}_{5}=3$ are also forbidden since values 1, 2 and 3 must be assigned to variables ${x}_{1}$, ${x}_{2}$ and ${x}_{3}$.

• Within the context of the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint, the assignment ${x}_{4}=3$ does not matter at all since the position of ${x}_{4}$ within $\beta ©{x}_{1}=1,{x}_{2}=2,{x}_{3}=3,{x}_{4}=3,{x}_{5}=4\beta ͺ$ (i.e.,Β positionΒ 4) does not belong to the set of variables positions $\left\{1,2,3,5\right\}$. We can only prune according to those variables that for sure should be assigned distinct values. Consequently ${x}_{3}=1$ and ${x}_{3}=2$ are forbidden since values 1 and 2 must already be assigned to ${x}_{1}$ and ${x}_{2}$. Finally the assignment ${x}_{5}=3$ is also forbidden since values 1, 2 and 3 must be assigned to ${x}_{1}$, ${x}_{2}$ and ${x}_{3}$.

B.Β Flow models for the Β and the Β constraints

##### Table 3.7.29. Domains of the variables and minimum and maximum number of occurrences of each value for the constraint of FigureΒ 3.7.29.
$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\left[{\mathrm{\pi \pi \pi \pi }}_{i},{\mathrm{\pi \pi \pi \pi ₯}}_{i}\right]$$i$$\left[{\mathrm{\pi \pi \pi \pi }}_{i},{\mathrm{\pi \pi \pi \pi ₯}}_{i}\right]$
1$\left\{1,2\right\}$5$\left\{1,2,3\right\}$1$\left[1,2\right]$5$\left[0,2\right]$
2$\left\{1,2\right\}$6$\left\{2,3,4,5\right\}$2$\left[1,2\right]$
3$\left\{1,2\right\}$7$\left\{3,5\right\}$3$\left[1,1\right]$
4$\left\{1,2\right\}$4$\left[0,2\right]$
##### Table 3.7.29. Domains of the variables and minimum and maximum number of occurrences of each value for the constraint of FigureΒ 3.7.29; to the entry named loop corresponds the interval $\left[\mathrm{\pi Ό\pi Έ\pi ½\pi »\pi Ύ\pi Ύ\pi Ώ},\mathrm{\pi Ό\pi °\pi \pi »\pi Ύ\pi Ύ\pi Ώ}\right]$ where $\mathrm{\pi Ό\pi Έ\pi ½\pi »\pi Ύ\pi Ύ\pi Ώ}$ and $\mathrm{\pi Ό\pi °\pi \pi »\pi Ύ\pi Ύ\pi Ώ}$ respectively correspond to the first and second arguments of the constraint.
$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\left[{\mathrm{\pi \pi \pi \pi }}_{i},{\mathrm{\pi \pi \pi \pi ₯}}_{i}\right]$$i$$\left[{\mathrm{\pi \pi \pi \pi }}_{i},{\mathrm{\pi \pi \pi \pi ₯}}_{i}\right]$
1$\left\{1,2\right\}$5$\left\{1,2\right\}$loop$\left[2,2\right]$4$\left[1,2\right]$
2$\left\{1,2\right\}$6$\left\{2,4,5\right\}$1$\left[1,2\right]$5$\left[0,2\right]$
3$\left\{1,2\right\}$7$\left\{3,4,5\right\}$2$\left[2,3\right]$
4$\left\{1,2,3\right\}$3$\left[1,1\right]$

FigureΒ 3.7.29 presents flow models for the and the constraints. Blue arcs represent feasible flows respectively corresponding to the solutions $\left(\beta ©{x}_{1}=1,{x}_{2}=1,{x}_{3}=2,{x}_{4}=2,{x}_{5}=3,{x}_{6}=5,{x}_{7}=5\beta ͺ,\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi \pi }-1\mathrm{\pi \pi \pi \pi ‘}-2,\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi \pi }-1\mathrm{\pi \pi \pi \pi ‘}-2,\mathrm{\pi \pi \pi }-3\mathrm{\pi \pi \pi \pi }-1\mathrm{\pi \pi \pi \pi ‘}-1,\mathrm{\pi \pi \pi }-4\mathrm{\pi \pi \pi \pi }-0\mathrm{\pi \pi \pi \pi ‘}-2,\mathrm{\pi \pi \pi }-5\mathrm{\pi \pi \pi \pi }-0\mathrm{\pi \pi \pi \pi ‘}-2\beta ͺ\right)$ and $\left(2,2,\beta ©{x}_{1}=1,{x}_{2}=2,{x}_{3}=2,{x}_{4}=2,{x}_{5}=1,{x}_{6}=4,{x}_{7}=3\beta ͺ,\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi \pi }-1\mathrm{\pi \pi \pi \pi ‘}-2,\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi \pi }-2\mathrm{\pi \pi \pi \pi ‘}-3,\mathrm{\pi \pi \pi }-3\mathrm{\pi \pi \pi \pi }-1\mathrm{\pi \pi \pi \pi ‘}-1,\mathrm{\pi \pi \pi }-4\mathrm{\pi \pi \pi \pi }-1\mathrm{\pi \pi \pi \pi ‘}-2,\mathrm{\pi \pi \pi }-5\mathrm{\pi \pi \pi \pi }-0\mathrm{\pi \pi \pi \pi ‘}-2\beta ͺ\right)$, while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution:

• Within the context of the constraint variables ${x}_{1}$, ${x}_{2}$, ${x}_{3}$ and ${x}_{4}$ take their values within the set $\left\{1,2\right\}$. Since each value in $\left\{1,2\right\}$ can be used at most 2 times, variables different from ${x}_{1}$, ${x}_{2}$, ${x}_{3}$, ${x}_{4}$ cannot be assigned a value in $\left\{1,2\right\}$. Consequently, , and . Since value 3 is the only remaining value for variable ${x}_{5}$, and since value 3 can be assigned to at most one variable, the assignments and are also forbidden.

• On the one hand we should have exactly two assignments of the form ${x}_{i}=i$ ($i\beta \left[1,7\right]$), since the first and second arguments of the constraint are both set to two. Since the two variables ${x}_{1}$ and ${x}_{2}$ are the only variables such that $i\beta \mathrm{\pi \pi \pi }\left({x}_{i}\right)$ we must have ${x}_{1}=1$ and ${x}_{2}=2$, i.e.Β  and .

• On the other hand, since we should have at least $1+2+1+1=5$ assignments of the form ${x}_{i}=j$ () and since only 5 variables ${x}_{i}$ (with $i\beta \left[3,7\right]$) can be assigned a value $j$ in $\left[1,4\right]$ with , these variables should not be assigned a value outside interval $\left[1,4\right]$, i.e.Β  and .

C.Β Flow models for the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi ’}$Β and theΒ $\mathrm{\pi \pi \pi \pi }$Β constraints

FigureΒ 3.7.30 presents flow models for the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi ’}$ and the $\mathrm{\pi \pi \pi \pi }$ constraints. Blue arcs represent feasible flows respectively corresponding to the solutions $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi ’}$$\left(\beta ©{x}_{1}=2,{x}_{2}=4,{x}_{3}=6\beta ͺ,\beta ©{y}_{1}=2,{y}_{2}=4\beta ͺ\right)$ and $\mathrm{\pi \pi \pi \pi }$$\left(\beta ©{x}_{1}=2,{x}_{2}=4,{x}_{3}=5\beta ͺ,\beta ©{y}_{1}=2,{y}_{2}=4,{y}_{3}=5\beta ͺ\right)$, while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution. Within the context of the $\mathrm{\pi \pi \pi \pi }$ constraint, the assignment ${x}_{1}=1$ is forbidden since $1\beta \mathrm{\pi \pi \pi }\left({y}_{1}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{2}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{3}\right)$. Consequently ${x}_{1}=2$ and, since ${y}_{1}$ is the only variable of $\left\{{y}_{1},{y}_{2},{y}_{3}\right\}$ that can be assigned value 2, the assignment ${y}_{1}=3$ is forbidden. Now since $3\beta \mathrm{\pi \pi \pi }\left({y}_{1}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{2}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{3}\right)$ the assignment ${x}_{2}=3$ is also forbidden. Finally ${x}_{3}=6$ is forbidden since $6\beta \mathrm{\pi \pi \pi }\left({y}_{1}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{2}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{3}\right)$.

##### Table 3.7.30. Domains of the variables for the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi ’}$ constraint of FigureΒ 3.7.30.
$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({y}_{i}\right)$
1$\left\{1,2\right\}$1$\left\{2,3\right\}$
2$\left\{3,4\right\}$2$\left\{4,5\right\}$
3$\left\{4,5,6\right\}$
##### Table 3.7.30. Domains of the variables for the $\mathrm{\pi \pi \pi \pi }$ constraint of FigureΒ 3.7.30.
$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({y}_{i}\right)$
1$\left\{1,2\right\}$1$\left\{2,3\right\}$
2$\left\{3,4\right\}$2$\left\{4,5\right\}$
3$\left\{4,5,6\right\}$3$\left\{4,5\right\}$

D.Β Flow model for the Β constraint

##### Table 3.7.30. Domains of the variables and minimum and maximum number of occurrences of each value for the constraint of FigureΒ 3.7.31.
$i$$\mathrm{\pi \pi \pi }\left({x}_{i}\right)$$i$$\mathrm{\pi \pi \pi }\left({y}_{i}\right)$$i$$\left[{\mathrm{\pi \pi \pi \pi }}_{i},{\mathrm{\pi \pi \pi \pi ₯}}_{i}\right]$$i$$\left[{\mathrm{\pi \pi \pi \pi }}_{i},{\mathrm{\pi \pi \pi \pi ₯}}_{i}\right]$
1$\left\{1,2\right\}$1$\left\{2,3\right\}$1$\left[0,1\right]$4$\left[2,3\right]$
2$\left\{3,4\right\}$2$\left\{4,5\right\}$2$\left[1,2\right]$5$\left[0,2\right]$
3$\left\{4,5,6\right\}$3$\left\{4,5\right\}$3$\left[0,3\right]$6$\left[0,1\right]$

FigureΒ 3.7.31 presents a flow model for the constraint. Blue arcs represent the feasible flow corresponding to the solution $\left(\beta ©{x}_{1}=2,{x}_{2}=4,{x}_{3}=4\beta ͺ,\beta ©{y}_{1}=2,{y}_{2}=4,{y}_{3}=4\beta ͺ,\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi \pi }-0\mathrm{\pi \pi \pi \pi ‘}-1,\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi \pi }-1\mathrm{\pi \pi \pi \pi ‘}-2,\mathrm{\pi \pi \pi }-3\mathrm{\pi \pi \pi \pi }-0\mathrm{\pi \pi \pi \pi ‘}-3,\mathrm{\pi \pi \pi }-4\mathrm{\pi \pi \pi \pi }-2\mathrm{\pi \pi \pi \pi ‘}-3,\mathrm{\pi \pi \pi }-5\mathrm{\pi \pi \pi \pi }-0\mathrm{\pi \pi \pi \pi ‘}-2,\mathrm{\pi \pi \pi }-6\mathrm{\pi \pi \pi \pi }-0\mathrm{\pi \pi \pi \pi ‘}-1\beta ͺ\right)$, while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution. The assignment ${x}_{1}=1$ is forbidden since $1\beta \mathrm{\pi \pi \pi }\left({y}_{1}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{2}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{3}\right)$. Consequently ${x}_{1}=2$ and, since ${y}_{1}$ is the only variable of $\left\{{y}_{1},{y}_{2},{y}_{3}\right\}$ that can be assigned value 2, the assignment ${y}_{1}=3$ is forbidden. Now since $3\beta \mathrm{\pi \pi \pi }\left({y}_{1}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{2}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{3}\right)$ the assignment ${x}_{2}=3$ is also forbidden. The assignment ${x}_{3}=6$ is forbidden since $6\beta \mathrm{\pi \pi \pi }\left({y}_{1}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{2}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({y}_{3}\right)$. Finally ${x}_{3}=5$, ${y}_{2}=5$ and ${y}_{3}=5$ are also forbidden since value 4 must be assigned to at least two variables.