5.48. cardinality_atmost_partition

DESCRIPTIONLINKSGRAPH
Origin

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

Constraint

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

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

π™°πšƒπ™Όπ™Ύπš‚πšƒ is the maximum number of time that values of a same partition of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚ are taken by the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
2,πšŸπšŠπš›-2,πšŸπšŠπš›-3,πšŸπšŠπš›-7,πšŸπšŠπš›-1,πšŸπšŠπš›-6,πšŸπšŠπš›-0,πš™-1,3,πš™-4,πš™-2,6

In this example, two variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=〈2,3,7,1,6,0βŒͺ are assigned values of the first partition, no variable is assigned a value of the second partition, and finally two variables are assigned values of the last partition. As a consequence, the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš–πš˜πšœπš_πš™πšŠπš›πšπš’πšπš’πš˜πš— constraint holds since its first argument π™°πšƒπ™Όπ™Ύπš‚πšƒ is assigned to the maximum number of occurrences 2.

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

  • Items of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚ are permutable.

  • Items of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚.πš™ are permutable.

See also

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

used in graph description: πš’πš—.

Keywords

characteristic of a constraint: partition.

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.48.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_πˆπƒ graph property, a vertex with the maximum number of predecessor is stressed with a double circle.

Figure 5.48.1. Initial and final graph of the πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš–πš˜πšœπš_πš™πšŠπš›πšπš’πšπš’πš˜πš— constraint
ctrs/cardinality_atmost_partitionActrs/cardinality_atmost_partitionB
(a) (b)