5.46. cardinality_atleast

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’.

Constraint

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

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

π™°πšƒπ™»π™΄π™°πš‚πšƒ is the minimum number of time that a value of πš…π™°π™»πš„π™΄πš‚ is taken by the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
(1,3,3,8,3,8)

In this example, values 3 and 8 are respectively used 2, and 1 times. The πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš•πšŽπšŠπšœπš constraint holds since its first argument π™°πšƒπ™»π™΄π™°πš‚πšƒ=1 is assigned to the minimum number of time that values 3 and 8 occur in the collection 〈3,3,8βŒͺ.

Typical
π™°πšƒπ™»π™΄π™°πš‚πšƒ>0
π™°πšƒπ™»π™΄π™°πš‚πšƒ<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
|πš…π™°π™»πš„π™΄πš‚|>0
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

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

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

Usage

An application of the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš•πšŽπšŠπšœπš constraint is to enforce a minimum use of values.

Remark

This is a restricted form of a variant of an πšŠπš–πš˜πš—πš constraint and of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint. In the original πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint, one specifies for each value its minimum and maximum number of occurrences.

Algorithm

See πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β [Regin96].

See also

generalisation: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (single πšŒπš˜πšžπš—πš πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by an individual πšŒπš˜πšžπš—πš πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ for each value).

Keywords

application area: assignment.

characteristic of a constraint: automaton, automaton with array of counters.

constraint type: value constraint.

filtering: arc-consistency.

final graph structure: acyclic, bipartite, no loop.

modelling: at least.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ πš…π™°π™»πš„π™΄πš‚

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,πšŸπšŠπš•πšžπšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›β‰ πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•
Graph property(ies)
πŒπ€π—_πˆπƒ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-π™°πšƒπ™»π™΄π™°πš‚πšƒ

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Using directly the graph property 𝐌𝐈𝐍_πˆπƒ = π™°πšƒπ™»π™΄π™°πš‚πšƒ, and replacing the disequality of the arc constraint by an equality does not work since it ignores values that are not assigned to any variable. This comes from the fact that isolated vertices are removed from the final graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.46.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_πˆπƒ graph property, the vertex with the maximum number of predecessor (i.e.,Β namely two predecessors) is stressed with a double circle. As a consequence the first argument π™°πšƒπ™»π™΄π™°πš‚πšƒ of the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš•πšŽπšŠπšœπš constraint is assigned to the total number of variables 3 minus 2.

Figure 5.46.1. Initial and final graph of the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš•πšŽπšŠπšœπš constraint
ctrs/cardinality_atleastActrs/cardinality_atleastB
(a) (b)
Automaton

FigureΒ 5.46.2 depicts the automaton associated with the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš•πšŽπšŠπšœπš constraint. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i and πš‚ i : πš…π™°πš i βˆˆπš…π™°π™»πš„π™΄πš‚β‡”πš‚ i .

Figure 5.46.2. Automaton of the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš•πšŽπšŠπšœπš constraint
ctrs/cardinality_atleast1