5.257. ordered_global_cardinality

DESCRIPTIONLINKSGRAPH
Origin

[PetitRegin09]

Constraint

πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

Usual name

πš˜πš›πšπšπšŒπšŒ

Synonym

πš˜πš›πšπšŽπš›πšŽπš_𝚐𝚌𝚌.

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš,πš˜πš–πšŠπš‘-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°π™»πš„π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,[πšŸπšŠπš•,πš˜πš–πšŠπš‘])
πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚜𝚎𝚚(πš…π™°π™»πš„π™΄πš‚,[πšŸπšŠπš•])
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘β‰₯0
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
Purpose

For each i∈[1,|πš…π™°π™»πš„π™΄πš‚|], the values of the corresponding set of values πš…π™°π™»πš„π™΄πš‚[j].πšŸπšŠπš• (i≀j≀|πš…π™°π™»πš„π™΄πš‚|) should be taken by at most πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πšŠπš‘ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

From that previous definition, the πš˜πš–πšŠπš‘ attributes are decreasing.

Example
2,0,1,0,0,πšŸπšŠπš•-0πš˜πš–πšŠπš‘-5,πšŸπšŠπš•-1πš˜πš–πšŠπš‘-3,πšŸπšŠπš•-2πš˜πš–πšŠπš‘-1

The πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint holds since the values of the three sets of values {0,1,2}, {1,2} and {2} are respectively used no more than 5, 3 and 1 times within the collection 〈2,0,1,0,0βŒͺ.

Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

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 v, we implicitly also use all values that are less than or equal to v. As depicted by FigureΒ 5.257.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 i a variable h i that gives the height of the cumulative profile at instant i. These variables h i are passed as the first argument of the πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint. Then the πš˜πš–πšŠπš‘ attribute of the j-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 πš…π™°π™»πš„π™΄πš‚[j].πšŸπšŠπš•. In FigureΒ 5.257.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.257.1. (A) Cumulative profile and (B) corresponding height variables
ctrs/ordered_global_cardinality1
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 O(|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|+|πš…π™°π™»πš„π™΄πš‚|) is described inΒ [PetitRegin09]. It is based on the equivalence between the following two statements:

  1. the πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint has a solution,

  2. all variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection assigned to their respective minimum value correspond to a solution of the πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint.

Reformulation

The πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’(βŒ©πšŸπšŠπš›-V 1 ,πšŸπšŠπš›-V 2 ,...,πšŸπšŠπš›-V |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| βŒͺ,

βŒ©πšŸπšŠπš•-v 1 πš˜πš–πšŠπš‘-o 1 ,πšŸπšŠπš•-v 2 πš˜πš–πšŠπš‘-o 2 ,...,πšŸπšŠπš•-v |πš…π™°π™»πš„π™΄πš‚| πš˜πš–πšŠπš‘-o |πš…π™°π™»πš„π™΄πš‚| βŒͺ) constraint can be reformulated into a πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’(βŒ©πšŸπšŠπš›-V 1 ,πšŸπšŠπš›-V 2 ,...,πšŸπšŠπš›-V |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| βŒͺ,βŒ©πšŸπšŠπš•-v 1 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-N 1 ,πšŸπšŠπš•-v 2 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-N 2 ,...,πšŸπšŠπš•-v |πš…π™°π™»πš„π™΄πš‚| πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-N |πš…π™°π™»πš„π™΄πš‚| βŒͺ) and |πš…π™°π™»πš„π™΄πš‚| sliding linear inequalities constraints of the form:

Β Β Β N 1 +N 2 +...+N |πš…π™°π™»πš„π™΄πš‚| ≀o 1 ,

Β Β Β Β Β Β Β Β Β N 2 +...+N |πš…π™°π™»πš„π™΄πš‚| ≀o 2 ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β ..................,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β N |πš…π™°π™»πš„π™΄πš‚| ≀o |πš…π™°π™»πš„π™΄πš‚| .

However, with the next example, T.Β Petit and J.-C.Β RΓ©gin have shown that this reformulation hinders propagation:

  1. V 1 ∈{0,1}, V 2 ∈{0,1}, V 3 ∈{0,1,2}, V 4 ∈{2,3}, V 5 ∈{2,3}.

  2. πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’( 〈V 1 ,V 2 ,V 3 ,V 4 ,V 5 βŒͺ, βŒ©πšŸπšŠπš•-1 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-N 1 , πšŸπšŠπš•-2 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-N 2 , πšŸπšŠπš•-3 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-N 3 βŒͺ ),

  3. N 1 +N 2 +N 3 ≀3∧N 2 +N 3 ≀2∧N 3 ≀2.

The previous reformulation does not remove value 2 from the domain of variable V 3 .

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).

root concept: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’.

Keywords

application area: assignment.

constraint type: value constraint, order constraint.

filtering: arc-consistency.

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.257.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.257.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.257.2. Initial and final graph of the πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint
ctrs/ordered_global_cardinalityActrs/ordered_global_cardinalityB
(a) (b)