5.139. global_cardinality_low_up

DESCRIPTIONLINKSGRAPH
Origin

Used for defining πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—.

Constraint

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

Synonyms

𝚐𝚌𝚌_πš•πš˜πš _πšžπš™, 𝚐𝚌𝚌.

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

Each value πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš• (1≀i≀|πš…π™°π™»πš„π™΄πš‚|) should be taken by at least πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πš’πš— and at most πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πšŠπš‘ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

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

The πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint holds since values 3, 5 and 6 are respectively used 2 (2≀2≀3), 0 (0≀0≀1) and 1 (1≀1≀2) times within the collection 〈3,3,8,6βŒͺ and since no constraint was specified for value 8.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
|πš…π™°π™»πš„π™΄πš‚|>1
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘>0
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› 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 β‰₯0.

  • πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘ 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.

Remark

Within the context of linear programmingΒ [Hooker07book] provides relaxations of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint.

Algorithm

A filtering algorithm achieving arc-consistency for the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint is given inΒ [Regin96].

The πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint is entailed if and only if for each value v equal to πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš• (with 1≀i≀|πš…π™°π™»πš„π™΄πš‚|) the following two conditions hold:

  1. The number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection assigned value v is greater than or equal to πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πš’πš—.

  2. The number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection that can potentially be assigned value v is less than or equal to πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πšŠπš‘.

Reformulation

A reformulation of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™, involving linear constraints, preserving bound-consistency was introduced inΒ [BessiereKatsirelosNarodytskaQuimperWalsh09IJCAI]. For each potential interval [l,u] of consecutive values this model uses |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| 0-1 variables B 1,l,u ,B 2,l,u ,...,B |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|,l,u for modelling the fact that each variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ is assigned a value within interval [l,u] (i.e.,Β βˆ€i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]:B i,l,u ⇔lβ‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›βˆ§πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›β‰€u), as well as one domain variable C l,u for counting how many values of [l,u] are assigned to variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ (i.e.Β C l,u =B 1,l,u +B 2,l,u +...+B |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|,l,u ). The lower and upper bounds of variable C l,u are respectively initially set with respect to the minimum and maximum number of possible occurrences of the values of interval [l,u]. Finally, assuming that s is the smallest value that can be assigned to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, the constraint C s,u =C s,k +C k+1,u is stated for each k∈[s,u-1].

Systems

globalCardinality in Choco.

Used in

πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—.

See also

common keyword: πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (assignment,counting constraint).

generalisation: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (πšπš’πš‘πšŽπš πš’πš—πšπšŽπš›πšŸπšŠπš• replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

implied by: πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (a πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint where the πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ are increasing), πšœπšŠπš–πšŽ_πšŠπš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™.

related: πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (restrictions are done on nested sets of values, all starting from first value).

shift of concept: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™_πš—πš˜_πš•πš˜πš˜πš™Β (assignment of a πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ to its position is ignored).

soft variant: πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™Β (a 𝚜𝚎𝚝 πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ defines the set of variables that are actually considered).

specialisation: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (each value should occur at most once).

system of constraints: πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—Β (one πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint for each sliding sequence of πš‚π™΄πš€ consecutive πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ).

Keywords

application area: assignment.

constraint type: value constraint, counting constraint.

filtering: flow, arc-consistency, bound-consistency, DFS-bottleneck.

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.139.1 shows the initial graphs associated with each value 3, 5 and 6 of the πš…π™°π™»πš„π™΄πš‚ collection of the Example slot. PartΒ (B) of FigureΒ 5.139.1 shows the two corresponding final graphs respectively associated with values 3 and 6 that are both assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection (since value 5 is not assigned to any variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection the final graph associated with value 5 is empty). Since we use the 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 graph property, the vertices of the final graphs are stressed in bold.

Figure 5.139.1. Initial and final graph of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint
ctrs/global_cardinality_low_upActrs/global_cardinality_low_upB
(a) (b)