### 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{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$ and the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}$ 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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, the $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$, the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}_\mathrm{𝚗𝚘}_\mathrm{𝚕𝚘𝚘𝚙}$, the $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}$, the $\mathrm{𝚜𝚊𝚖𝚎}$, and the $\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚊𝚗𝚍}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraints.

A. Flow models for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ and the $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints

Figure 3.7.28 presents flow models for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ and the $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints. Blue arcs represent feasible flows respectively corresponding to the solutions $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(〈{x}_{1}=1,{x}_{2}=2,{x}_{3}=3,{x}_{4}=4,{x}_{5}=5〉\right)$ and $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\left\{\mathbf{1},\mathbf{2},\mathbf{3},\mathbf{5}\right\},〈{x}_{1}=1,{x}_{2}=2,{x}_{3}=3,{x}_{4}=3,{x}_{5}=4〉\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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ and $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints.

##### Table 3.7.27. Domains of the variables for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint of Figure 3.7.28.
$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\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{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint of Figure 3.7.28. The lower and upper bounds of the set variable corresponding to the first argument of the $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\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\}$
##### Figure 3.7.28. Flow models for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ and the $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints described in Tables 3.7.27 and 3.7.27: in both cases a first layer consists of the variables of the constraint and a second layer corresponds to the values that can be assigned to the variables; each arc has a lower and upper capacity regarding the flow it can carry; all variables ${x}_{i}$ (with $i\in \left[1,5\right]$) such that the minimum capacity of the arc from $s$ to ${x}_{i}$ is equal to 1 must be assigned distinct values. • Within the context of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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{𝚘𝚙𝚎𝚗}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint, the assignment ${x}_{4}=3$ does not matter at all since the position of ${x}_{4}$ within $〈{x}_{1}=1,{x}_{2}=2,{x}_{3}=3,{x}_{4}=3,{x}_{5}=4〉$ (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}$.

##### Figure 3.7.29. Flow models for the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ and the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}_\mathrm{𝚗𝚘}_\mathrm{𝚕𝚘𝚘𝚙}$ constraints described in Tables 3.7.29 and 3.7.29: in both cases a first layer consists of the variables of the constraint and a second layer corresponds to the values that can be assigned to the variables (in the second model, the loop node represents an anonymous value $i$ corresponding to assignments of the form ${x}_{i}=i$); each arc has a lower and upper capacity regarding the flow it can carry; arcs entering a node associated with a variable must carry a flow of 1 since each variable must be assigned a single value, while arcs exiting a node associated with a value have a capacity set accordingly the last argument of the constraint (i.e., the collection of values $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$). ##### Table 3.7.29. Domains of the variables and minimum and maximum number of occurrences of each value for the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint of Figure 3.7.29.
$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\left[{\mathrm{𝑜𝑚𝑖𝑛}}_{i},{\mathrm{𝑜𝑚𝑎𝑥}}_{i}\right]$$i$$\left[{\mathrm{𝑜𝑚𝑖𝑛}}_{i},{\mathrm{𝑜𝑚𝑎𝑥}}_{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 $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}_\mathrm{𝚗𝚘}_\mathrm{𝚕𝚘𝚘𝚙}$ constraint of Figure 3.7.29; to the entry named loop corresponds the interval $\left[\mathrm{𝙼𝙸𝙽𝙻𝙾𝙾𝙿},\mathrm{𝙼𝙰𝚇𝙻𝙾𝙾𝙿}\right]$ where $\mathrm{𝙼𝙸𝙽𝙻𝙾𝙾𝙿}$ and $\mathrm{𝙼𝙰𝚇𝙻𝙾𝙾𝙿}$ respectively correspond to the first and second arguments of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}_\mathrm{𝚗𝚘}_\mathrm{𝚕𝚘𝚘𝚙}$ constraint.
$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\left[{\mathrm{𝑜𝑚𝑖𝑛}}_{i},{\mathrm{𝑜𝑚𝑎𝑥}}_{i}\right]$$i$$\left[{\mathrm{𝑜𝑚𝑖𝑛}}_{i},{\mathrm{𝑜𝑚𝑎𝑥}}_{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 $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ and the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}_\mathrm{𝚗𝚘}_\mathrm{𝚕𝚘𝚘𝚙}$ constraints. Blue arcs represent feasible flows respectively corresponding to the solutions $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ $\left(〈{x}_{1}=1,{x}_{2}=1,{x}_{3}=2,{x}_{4}=2,{x}_{5}=3,{x}_{6}=5,{x}_{7}=5〉,〈\mathrm{𝚟𝚊𝚕}-1\mathrm{𝚘𝚖𝚒𝚗}-1\mathrm{𝚘𝚖𝚊𝚡}-2,\mathrm{𝚟𝚊𝚕}-2\mathrm{𝚘𝚖𝚒𝚗}-1\mathrm{𝚘𝚖𝚊𝚡}-2,\mathrm{𝚟𝚊𝚕}-3\mathrm{𝚘𝚖𝚒𝚗}-1\mathrm{𝚘𝚖𝚊𝚡}-1,\mathrm{𝚟𝚊𝚕}-4\mathrm{𝚘𝚖𝚒𝚗}-0\mathrm{𝚘𝚖𝚊𝚡}-2,\mathrm{𝚟𝚊𝚕}-5\mathrm{𝚘𝚖𝚒𝚗}-0\mathrm{𝚘𝚖𝚊𝚡}-2〉\right)$ and $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}_\mathrm{𝚗𝚘}_\mathrm{𝚕𝚘𝚘𝚙}$ $\left(2,2,〈{x}_{1}=1,{x}_{2}=2,{x}_{3}=2,{x}_{4}=2,{x}_{5}=1,{x}_{6}=4,{x}_{7}=3〉,〈\mathrm{𝚟𝚊𝚕}-1\mathrm{𝚘𝚖𝚒𝚗}-1\mathrm{𝚘𝚖𝚊𝚡}-2,\mathrm{𝚟𝚊𝚕}-2\mathrm{𝚘𝚖𝚒𝚗}-2\mathrm{𝚘𝚖𝚊𝚡}-3,\mathrm{𝚟𝚊𝚕}-3\mathrm{𝚘𝚖𝚒𝚗}-1\mathrm{𝚘𝚖𝚊𝚡}-1,\mathrm{𝚟𝚊𝚕}-4\mathrm{𝚘𝚖𝚒𝚗}-1\mathrm{𝚘𝚖𝚊𝚡}-2,\mathrm{𝚟𝚊𝚕}-5\mathrm{𝚘𝚖𝚒𝚗}-0\mathrm{𝚘𝚖𝚊𝚡}-2〉\right)$, while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution:

• Within the context of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ 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, ${x}_{5}\ne 1$, ${x}_{5}\ne 2$ and ${x}_{6}\ne 2$. 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 ${x}_{6}\ne 3$ and ${x}_{7}\ne 3$ are also forbidden.

• On the one hand we should have exactly two assignments of the form ${x}_{i}=i$ ($i\in \left[1,7\right]$), since the first and second arguments of the constraint $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}_\mathrm{𝚗𝚘}_\mathrm{𝚕𝚘𝚘𝚙}$ are both set to two. Since the two variables ${x}_{1}$ and ${x}_{2}$ are the only variables such that $i\in \mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$ we must have ${x}_{1}=1$ and ${x}_{2}=2$, i.e. ${x}_{1}\ne 2$ and ${x}_{2}\ne 1$.

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

C. Flow models for the $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}$ and the $\mathrm{𝚜𝚊𝚖𝚎}$ constraints

Figure 3.7.30 presents flow models for the $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}$ and the $\mathrm{𝚜𝚊𝚖𝚎}$ constraints. Blue arcs represent feasible flows respectively corresponding to the solutions $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}$$\left(〈{x}_{1}=2,{x}_{2}=4,{x}_{3}=6〉,〈{y}_{1}=2,{y}_{2}=4〉\right)$ and $\mathrm{𝚜𝚊𝚖𝚎}$$\left(〈{x}_{1}=2,{x}_{2}=4,{x}_{3}=5〉,〈{y}_{1}=2,{y}_{2}=4,{y}_{3}=5〉\right)$, while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution. Within the context of the $\mathrm{𝚜𝚊𝚖𝚎}$ constraint, the assignment ${x}_{1}=1$ is forbidden since $1\notin \mathrm{𝑑𝑜𝑚}\left({y}_{1}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{2}\right)\cup \mathrm{𝑑𝑜𝑚}\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\notin \mathrm{𝑑𝑜𝑚}\left({y}_{1}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{2}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{3}\right)$ the assignment ${x}_{2}=3$ is also forbidden. Finally ${x}_{3}=6$ is forbidden since $6\notin \mathrm{𝑑𝑜𝑚}\left({y}_{1}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{2}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{3}\right)$.

##### Figure 3.7.30. Flow models for the $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}$ and the $\mathrm{𝚜𝚊𝚖𝚎}$ constraints described in Tables 3.7.30 and 3.7.30: in both cases a first layer consists of the variables ${x}_{i}$ of the first argument of both constraints, a second layer corresponds to the values that can be assigned to the variables ${x}_{i}$ and ${y}_{i}$ (i.e., the first and second arguments), and a third layer consists of the variables ${y}_{i}$ of the second argument of both constraints; there is an arc from a variable ${x}_{i}$ (resp. ${y}_{i}$) to a value $v$ if, and only if, value $v$ can be assigned to variable ${x}_{i}$ (resp. ${y}_{i}$); each arc has a lower and upper capacity regarding the flow it can carry; since for both constraints each value assigned to a variable of the second argument must also correspond to a value assigned to a variable of the first argument the arcs exiting the ${y}_{i}$ must carry a flow of 1. ##### Table 3.7.30. Domains of the variables for the $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}$ constraint of Figure 3.7.30.
$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\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{𝚜𝚊𝚖𝚎}$ constraint of Figure 3.7.30.
$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\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\}$
##### Table 3.7.30. Domains of the variables and minimum and maximum number of occurrences of each value for the $\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚊𝚗𝚍}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint of Figure 3.7.31.
$i$$\mathrm{𝑑𝑜𝑚}\left({x}_{i}\right)$$i$$\mathrm{𝑑𝑜𝑚}\left({y}_{i}\right)$$i$$\left[{\mathrm{𝑜𝑚𝑖𝑛}}_{i},{\mathrm{𝑜𝑚𝑎𝑥}}_{i}\right]$$i$$\left[{\mathrm{𝑜𝑚𝑖𝑛}}_{i},{\mathrm{𝑜𝑚𝑎𝑥}}_{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 $\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚊𝚗𝚍}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint. Blue arcs represent the feasible flow corresponding to the solution $\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚊𝚗𝚍}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ $\left(〈{x}_{1}=2,{x}_{2}=4,{x}_{3}=4〉,〈{y}_{1}=2,{y}_{2}=4,{y}_{3}=4〉,〈\mathrm{𝚟𝚊𝚕}-1\mathrm{𝚘𝚖𝚒𝚗}-0\mathrm{𝚘𝚖𝚊𝚡}-1,\mathrm{𝚟𝚊𝚕}-2\mathrm{𝚘𝚖𝚒𝚗}-1\mathrm{𝚘𝚖𝚊𝚡}-2,\mathrm{𝚟𝚊𝚕}-3\mathrm{𝚘𝚖𝚒𝚗}-0\mathrm{𝚘𝚖𝚊𝚡}-3,\mathrm{𝚟𝚊𝚕}-4\mathrm{𝚘𝚖𝚒𝚗}-2\mathrm{𝚘𝚖𝚊𝚡}-3,\mathrm{𝚟𝚊𝚕}-5\mathrm{𝚘𝚖𝚒𝚗}-0\mathrm{𝚘𝚖𝚊𝚡}-2,\mathrm{𝚟𝚊𝚕}-6\mathrm{𝚘𝚖𝚒𝚗}-0\mathrm{𝚘𝚖𝚊𝚡}-1〉\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\notin \mathrm{𝑑𝑜𝑚}\left({y}_{1}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{2}\right)\cup \mathrm{𝑑𝑜𝑚}\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\notin \mathrm{𝑑𝑜𝑚}\left({y}_{1}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{2}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{3}\right)$ the assignment ${x}_{2}=3$ is also forbidden. The assignment ${x}_{3}=6$ is forbidden since $6\notin \mathrm{𝑑𝑜𝑚}\left({y}_{1}\right)\cup \mathrm{𝑑𝑜𝑚}\left({y}_{2}\right)\cup \mathrm{𝑑𝑜𝑚}\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.

##### Figure 3.7.31. Flow model for the $\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚊𝚗𝚍}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint described in Table 3.7.30: in both cases a first layer consists of the variables ${x}_{i}$ of the first argument of the constraint, a second (resp. third) layer corresponds to the values that can be assigned to the variables ${x}_{i}$ (resp. ${y}_{i}$), and a fourth layer consists of the variables ${y}_{i}$ of the second argument of the constraint; each arc has a lower and upper capacity regarding the flow it can carry; values are duplicated in two layers in order to model the minimum and maximum number of occurrences of each value; there is an arc from a variable ${x}_{i}$ (resp. ${y}_{i}$) to a value $v$ if, and only if, value $v$ can be assigned to variable ${x}_{i}$ (resp. ${y}_{i}$); since each variable ${x}_{i}$ (resp. ${y}_{i}$) must be assigned a value the arcs exiting $s$ (resp. entering $t$) must carry a flow of 1. 