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
and
,
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.
| | | | | |
1 | | 3 | | 5 | |
2 | | 4 | | | |
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
, and , where is a
shortcut for denoting both bounds.
| | | | | |
1 | | 3 | | 5 | |
2 | | 4 | | | |
Within the context of the constraint
the assignments , and are forbidden since values 1 and 2 must
already be assigned to variables and . Finally the assignments and
are also forbidden since values 1, 2 and 3 must be assigned to variables ,
and .
Within the context of the
constraint, the assignment does not matter at all since the position of within
(i.e.,Β positionΒ 4) does not belong to the
set of variables positions .
We can only prune according to those variables that for sure should be assigned distinct values.
Consequently and are forbidden since values 1 and 2 must already be
assigned to and . Finally the assignment is also forbidden since values
1, 2 and 3 must be assigned to , and .
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.
| | | | | | | |
1 | | 5 | | 1 | | 5 | |
2 | | 6 | | 2 | | | |
3 | | 7 | | 3 | | | |
4 | | | | 4 | | | |
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.
| | | | | | | |
1 | | 5 | | loop | | 4 | |
2 | | 6 | | 1 | | 5 | |
3 | | 7 | | 2 | | | |
4 | | | | 3 | | | |
FigureΒ 3.7.29 presents flow models for
the and
the
constraints. Blue arcs represent feasible flows respectively corresponding to the solutions
and
,
while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution:
Within the context of the
constraint variables , , and take their values within the set .
Since each value in can be used at most 2 times, variables different from
, , , cannot be assigned a value in . Consequently,
, and . Since value 3 is the only remaining
value for variable , 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 (),
since the first and second arguments of the constraint
are both set to two.
Since the two variables and are the only variables such that
we must have and , i.e.Β and .
On the other hand, since we should have at least assignments of the form
() and since only 5 variables (with ) can be assigned a value in with ,
these variables should not be assigned a value outside interval , i.e.Β and .
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
and
,
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
is forbidden since .
Consequently and, since is the only variable of that can be
assigned value 2, the assignment is forbidden.
Now since the assignment
is also forbidden.
Finally is forbidden since .
Table 3.7.30. Domains of the variables for
the constraint of FigureΒ 3.7.30.
| | | |
1 | | 1 | |
2 | | 2 | |
3 | | | |
Table 3.7.30. Domains of the variables for
the constraint of FigureΒ 3.7.30.
| | | |
1 | | 1 | |
2 | | 2 | |
3 | | 3 | |
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.
| | | | | | | |
1 | | 1 | | 1 | | 4 | |
2 | | 2 | | 2 | | 5 | |
3 | | 3 | | 3 | | 6 | |
FigureΒ 3.7.31 presents a flow model for the
constraint.
Blue arcs represent the feasible flow corresponding to the solution
,
while red arcs correspond to arcs that cannot carry any flow if the constraint has a solution.
The assignment is forbidden since .
Consequently and, since is the only variable of that can be
assigned value 2, the assignment is forbidden.
Now since the assignment
is also forbidden.
The assignment is forbidden since .
Finally , and are also forbidden since value 4 must be assigned to at least two
variables.