5.308. ordered_global_cardinality
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Usual name
- Synonym
.
- Arguments
- Restrictions
- Purpose
For each , the values of the corresponding set of values should be taken by at most variables of the collection.
From that previous definition, the attributes are decreasing.
- Example
-
The constraint holds since the values of the three sets of values , and are respectively used no more than 5, 3 and 1 times within the collection .
- Symmetry
Items of are permutable.
- Arg. properties
Contractible wrt. .
- Usage
The can be used in order to restrict the way we assign the values of the collection to the variables of the collection. It expresses the fact that, when we use a value , we implicitly also use all values that are less than or equal to . As depicted by FigureΒ 5.308.1 this is for instance the case for a soft cumulative constraint where we want to control the shape of cumulative profile by providing for each instant a variable that gives the height of the cumulative profile at instant . These variables are passed as the first argument of the constraint. Then the attribute of the -th item of the collection gives the maximum number of instants for which the height of the cumulative profile is greater than or equal to value . In FigureΒ 5.308.1 we should have:
no more than 1 height variable greater than or equal to 2,
no more than 3 height variables greater than or equal to 1,
no more than 5 height variables greater than or equal to 0.
Figure 5.308.1. (A)Β A cumulative profile wrt two tasks β and β‘, and its corresponding height variables , giving at each instant how many resource is used (B)Β profile of value utilisation of the height variables (e.g.,Β value 1 is assigned to variables , , and therefore used three times)
- Remark
The original definition of the constraint mentions a third argument, namely the minimum number of occurrences of the smallest value. We omit it since it is redundant.
An other closely related constraint, the constraint was introduced inΒ [PetitRegin09] in order to model the fact that overloads costs may depend of the instant where they occur.
- Algorithm
A filtering algorithm achieving arc-consistency in is described inΒ [PetitRegin09]. It is based on the equivalence between the following two statements:
the constraint has a solution,
all variables of the collection assigned to their respective minimum value correspond to a solution to the constraint.
- Reformulation
The
constraint can be reformulated into a and sliding linear inequalities constraints of the form:
Β Β Β ,
Β Β Β Β Β Β Β Β Β ,
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β ,
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β .
However, with the next example, T.Β Petit and J.-C.Β RΓ©gin have shown that this reformulation hinders propagation:
, , , , .
,
.
The previous reformulation does not remove value 2 from the domain of variable .
- See also
related: Β (controlling the shape of the cumulative profile for breaking symmetry), , Β (the order is imposed on the main variables, and not on the count variables).
- Keywords
For all items of :
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
Since we want to express one unary constraint for each value we use the βFor all items of β iterator. PartΒ (A) of FigureΒ 5.308.2 shows the initial graphs associated with each value 0, 1 and 2 of the collection of the Example slot. PartΒ (B) of FigureΒ 5.308.2 shows the corresponding final graph associated with value 0. Since we use the graph property, the vertices of the final graph is stressed in bold.
Figure 5.308.2. Initial and final graph of the constraint
(a) (b)