5.47. cardinality_atmost

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

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

Constraint

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

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

π™°πšƒπ™Όπ™Ύπš‚πšƒ is the maximum number of occurrences of each value of πš…π™°π™»πš„π™΄πš‚ within the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
2,2,1,7,1,2,5,7,2,9

In this example, values 5, 7, 2 and 9 occur respectively 0, 1, 2 and 0 times within the collection 〈2,1,7,1,2βŒͺ. As a consequence, the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš–πš˜πšœπš constraint holds since its first argument π™°πšƒπ™Όπ™Ύπš‚πšƒ is assigned to the maximum number of occurrences 2.

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 maximum use of values.

Remark

This is a restricted form of a variant of the πšŠπš–πš˜πš—πš 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).

implied by: πšŠπš–πš˜πš—πš.

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

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•
Graph property(ies)
πŒπ€π—_πˆπƒ=π™°πšƒπ™Όπ™Ύπš‚πšƒ

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

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.47.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_πˆπƒ graph property, the vertex that has the maximum number of predecessor is stressed with a double circle.

Figure 5.47.1. Initial and final graph of the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš–πš˜πšœπš constraint
ctrs/cardinality_atmostActrs/cardinality_atmostB
(a) (b)
Automaton

FigureΒ 5.47.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.47.2. Automaton of the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš–πš˜πšœπš constraint
ctrs/cardinality_atmost1