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 πšŠπš–πš˜πš—πš_𝚜𝚎𝚚 and the πšœπš•πš’πšπš’πš—πš_πšœπšžπš– 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 πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, the πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™, the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™_πš—πš˜_πš•πš˜πš˜πš™, the 𝚞𝚜𝚎𝚍_πš‹πš’, the πšœπšŠπš–πšŽ, and the πšœπšŠπš–πšŽ_πšŠπš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraints.

A.Β Flow models forΒ theΒ πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ and theΒ πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ constraints

FigureΒ 3.7.28 presents flow models for the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš and the πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints. Blue arcs represent feasible flows respectively corresponding to the solutions πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(〈x 1 =1, x 2 =2, x 3 =3, x 4 =4, x 5 =5βŒͺ) and πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš({1,2,3,5},〈x 1 =1, x 2 =2, x 3 =3, x 4 =3, x 5 =4βŒͺ), 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 πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš and πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints.

Table 3.7.27. Domains of the variables for the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint of FigureΒ 3.7.28.
iπ‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(x i )
1{1,2}3{1,2,3}5{3,4,5,6}
2{1,2}4{2,3,4,5}
Table 3.7.27. Domains of the variables for the πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint of FigureΒ 3.7.28. The lower and upper bounds of the set variable corresponding to the first argument of the πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint are respectively equal to set of variables positions {1,2,3,5}, and {1,2,3,4,5}, where {1,2,3,4,5} is a shortcut for denoting both bounds.
iπ‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(x i )
1{1,2}3{1,2,3}5{3,4}
2{1,2}4{2,3}
Figure 3.7.28. Flow models for the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš and the πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš 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∈[1,5]) such that the minimum capacity of the arc from s to x i is equal to 1 must be assigned distinct values.
ctrs/preface-168-tikz

B.Β Flow models for the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™Β and the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™_πš—πš˜_πš•πš˜πš˜πš™Β constraints

Figure 3.7.29. Flow models for the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ and the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™_πš—πš˜_πš•πš˜πš˜πš™ 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 πš…π™°π™»πš„π™΄πš‚).
ctrs/preface-169-tikz
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π‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(x i )i[π‘œπ‘šπ‘–π‘› i ,π‘œπ‘šπ‘Žπ‘₯ i ]i[π‘œπ‘šπ‘–π‘› i ,π‘œπ‘šπ‘Žπ‘₯ i ]
1{1,2}5{1,2,3}1[1,2]5[0,2]
2{1,2}6{2,3,4,5}2[1,2]
3{1,2}7{3,5}3[1,1]
4{1,2}4[0,2]
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 [𝙼𝙸𝙽𝙻𝙾𝙾𝙿,π™Όπ™°πš‡π™»π™Ύπ™Ύπ™Ώ] where 𝙼𝙸𝙽𝙻𝙾𝙾𝙿 and π™Όπ™°πš‡π™»π™Ύπ™Ύπ™Ώ respectively correspond to the first and second arguments of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™_πš—πš˜_πš•πš˜πš˜πš™ constraint.
iπ‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(x i )i[π‘œπ‘šπ‘–π‘› i ,π‘œπ‘šπ‘Žπ‘₯ i ]i[π‘œπ‘šπ‘–π‘› i ,π‘œπ‘šπ‘Žπ‘₯ i ]
1{1,2}5{1,2}loop[2,2]4[1,2]
2{1,2}6{2,4,5}1[1,2]5[0,2]
3{1,2}7{3,4,5}2[2,3]
4{1,2,3}3[1,1]

FigureΒ 3.7.29 presents flow models for the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ and the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™_πš—πš˜_πš•πš˜πš˜πš™ constraints. Blue arcs represent feasible flows respectively corresponding to the solutions πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ (〈x 1 =1,x 2 =1,x 3 =2,x 4 =2,x 5 =3,x 6 =5,x 7 =5βŒͺ,βŒ©πšŸπšŠπš•-1 πš˜πš–πš’πš—-1 πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-2 πš˜πš–πš’πš—-1 πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-3 πš˜πš–πš’πš—-1 πš˜πš–πšŠπš‘-1,πšŸπšŠπš•-4 πš˜πš–πš’πš—-0 πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-5 πš˜πš–πš’πš—-0 πš˜πš–πšŠπš‘-2βŒͺ) and πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™_πš—πš˜_πš•πš˜πš˜πš™ (2,2,〈x 1 =1,x 2 =2,x 3 =2,x 4 =2,x 5 =1,x 6 =4,x 7 =3βŒͺ,βŒ©πšŸπšŠπš•-1 πš˜πš–πš’πš—-1 πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-2 πš˜πš–πš’πš—-2 πš˜πš–πšŠπš‘-3,πšŸπšŠπš•-3 πš˜πš–πš’πš—-1 πš˜πš–πšŠπš‘-1,πšŸπšŠπš•-4 πš˜πš–πš’πš—-1 πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-5 πš˜πš–πš’πš—-0 πš˜πš–πšŠπš‘-2βŒͺ), while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution:

C.Β Flow models for the 𝚞𝚜𝚎𝚍_πš‹πš’Β and theΒ πšœπšŠπš–πšŽΒ constraints

FigureΒ 3.7.30 presents flow models for the 𝚞𝚜𝚎𝚍_πš‹πš’ and the πšœπšŠπš–πšŽ constraints. Blue arcs represent feasible flows respectively corresponding to the solutions 𝚞𝚜𝚎𝚍_πš‹πš’(〈x 1 =2,x 2 =4,x 3 =6βŒͺ,〈y 1 =2,y 2 =4βŒͺ) and πšœπšŠπš–πšŽ(〈x 1 =2,x 2 =4,x 3 =5βŒͺ,〈y 1 =2,y 2 =4,y 3 =5βŒͺ), while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution. Within the context of the πšœπšŠπš–πšŽ constraint, the assignment x 1 =1 is forbidden since 1βˆ‰π‘‘π‘œπ‘š(y 1 )βˆͺπ‘‘π‘œπ‘š(y 2 )βˆͺπ‘‘π‘œπ‘š(y 3 ). Consequently x 1 =2 and, since y 1 is the only variable of {y 1 ,y 2 ,y 3 } that can be assigned value 2, the assignment y 1 =3 is forbidden. Now since 3βˆ‰π‘‘π‘œπ‘š(y 1 )βˆͺπ‘‘π‘œπ‘š(y 2 )βˆͺπ‘‘π‘œπ‘š(y 3 ) the assignment x 2 =3 is also forbidden. Finally x 3 =6 is forbidden since 6βˆ‰π‘‘π‘œπ‘š(y 1 )βˆͺπ‘‘π‘œπ‘š(y 2 )βˆͺπ‘‘π‘œπ‘š(y 3 ).

Figure 3.7.30. Flow models for the 𝚞𝚜𝚎𝚍_πš‹πš’ and the πšœπšŠπš–πšŽ 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.
ctrs/preface-170-tikz
Table 3.7.30. Domains of the variables for the 𝚞𝚜𝚎𝚍_πš‹πš’ constraint of FigureΒ 3.7.30.
iπ‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(y i )
1{1,2}1{2,3}
2{3,4}2{4,5}
3{4,5,6}
Table 3.7.30. Domains of the variables for the πšœπšŠπš–πšŽ constraint of FigureΒ 3.7.30.
iπ‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(y i )
1{1,2}1{2,3}
2{3,4}2{4,5}
3{4,5,6}3{4,5}

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π‘‘π‘œπ‘š(x i )iπ‘‘π‘œπ‘š(y i )i[π‘œπ‘šπ‘–π‘› i ,π‘œπ‘šπ‘Žπ‘₯ i ]i[π‘œπ‘šπ‘–π‘› i ,π‘œπ‘šπ‘Žπ‘₯ i ]
1{1,2}1{2,3}1[0,1]4[2,3]
2{3,4}2{4,5}2[1,2]5[0,2]
3{4,5,6}3{4,5}3[0,3]6[0,1]

FigureΒ 3.7.31 presents a flow model for the πšœπšŠπš–πšŽ_πšŠπš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint. Blue arcs represent the feasible flow corresponding to the solution πšœπšŠπš–πšŽ_πšŠπš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ (〈x 1 =2,x 2 =4,x 3 =4βŒͺ,〈y 1 =2,y 2 =4,y 3 =4βŒͺ,βŒ©πšŸπšŠπš•-1 πš˜πš–πš’πš—-0 πš˜πš–πšŠπš‘-1,πšŸπšŠπš•-2 πš˜πš–πš’πš—-1 πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-3 πš˜πš–πš’πš—-0 πš˜πš–πšŠπš‘-3,πšŸπšŠπš•-4 πš˜πš–πš’πš—-2 πš˜πš–πšŠπš‘-3,πšŸπšŠπš•-5 πš˜πš–πš’πš—-0 πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-6 πš˜πš–πš’πš—-0 πš˜πš–πšŠπš‘-1βŒͺ), 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βˆ‰π‘‘π‘œπ‘š(y 1 )βˆͺπ‘‘π‘œπ‘š(y 2 )βˆͺπ‘‘π‘œπ‘š(y 3 ). Consequently x 1 =2 and, since y 1 is the only variable of {y 1 ,y 2 ,y 3 } that can be assigned value 2, the assignment y 1 =3 is forbidden. Now since 3βˆ‰π‘‘π‘œπ‘š(y 1 )βˆͺπ‘‘π‘œπ‘š(y 2 )βˆͺπ‘‘π‘œπ‘š(y 3 ) the assignment x 2 =3 is also forbidden. The assignment x 3 =6 is forbidden since 6βˆ‰π‘‘π‘œπ‘š(y 1 )βˆͺπ‘‘π‘œπ‘š(y 2 )βˆͺπ‘‘π‘œπ‘š(y 3 ). 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 πšœπšŠπš–πšŽ_πšŠπš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ 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.
ctrs/preface-171-tikz