5.336. same_and_global_cardinality_low_up
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
The variables of the collection correspond to the variables of the collection according to a permutation. In addition, each value (with ) should be taken by at least and at most variables of the collection. Finally, each variable of should be assigned a value of (with ).
- Example
-
The constraint holds since:
The values 1, 9, 1, 5, 2, 1 assigned to correspond to a permutation of the values 9, 1, 1, 1, 2, 5 assigned to .
The values 1, 2, 5, 7 and 6 are respectively used 3 (), 1 (), 1 (), 0 () and 1 () times.
- Typical
- Symmetries
Arguments are permutable w.r.t. permutation .
Items of are permutable.
Items of are permutable.
An occurrence of a value of or that does not belong to can be replaced by any other value that also does not belong to .
Items of are permutable.
can be decreased to any value .
can be increased to any value .
All occurrences of two distinct values in , or can be swapped; all occurrences of a value in , or can be renamed to any unused value.
- Arg. properties
Contractible wrt. .
- Usage
The constraint can be used for modelling the following assignment problem with a single constraint. The organisation Doctors Without Borders has a list of doctors and a list of nurses, each of whom volunteered to go on one rescue mission. Each volunteer specifies a list of possible dates and each mission should include one doctor and one nurse. In addition we have for each date the minimum and maximum number of missions that should be effectively done. The task is to produce a list of pairs such that each pair includes a doctor and a nurse who are available on the same date and each volunteer appears in exactly one pair so that for each day we build the required number of missions.
- Algorithm
InΒ [BeldiceanuKatrielThiel05b], the flow network that was used to model the constraint Β [BeldiceanuKatrielThiel04a], [BeldiceanuKatrielThiel04b] is extended to support the cardinalities. FigureΒ 3.7.31 illustrates this flow model. Then, algorithms are developed to compute arc-consistency and bound-consistency.
- See also
generalisation: Β ( replaced by ).
implies: , , .
- Keywords
-
combinatorial object: permutation, multiset.
constraint arguments: constraint between two collections of variables.
constraint type: value constraint.
filtering: bound-consistency, arc-consistency, flow.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
For all items of :
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.336.1 respectively show the initial and final graph associated with the first graph constraint of the Example slot. Since we use the and graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint.
Figure 5.336.1. Initial and final graph of the constraint
(a) (b)