5.284. same_partition

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšœπšŠπš–πšŽ.

Constraint

πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚)

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

For each integer i in [1,|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|], let 𝑁1 i (respectively 𝑁2 i ) denote the number of variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 (respectively πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) that take their value in the i th partition of the collection π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚. For all i in [1,|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|] we have 𝑁1 i =𝑁2 i .

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

The different values of the collection 〈1,2,6,3,1,2βŒͺ are respectively associated with the partitions πš™-〈1,3βŒͺ, πš™-〈2,6βŒͺ, πš™-〈2,6βŒͺ, πš™-〈1,3βŒͺ, πš™-〈1,3βŒͺ, and πš™-〈2,6βŒͺ. Therefore partitions πš™-〈1,3βŒͺ and πš™-〈2,6βŒͺ are respectively used 3 and 3 times. Similarly, the different values of the collection 〈6,6,2,3,1,3βŒͺ are respectively associated with the partitions πš™-〈2,6βŒͺ, πš™-〈2,6βŒͺ, πš™-〈2,6βŒͺ, πš™-〈1,3βŒͺ, πš™-〈1,3βŒͺ, and πš™-〈1,3βŒͺ. As before partitions πš™-〈1,3βŒͺ and πš™-〈2,6βŒͺ are respectively used 3 and 3 times. Consequently the πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš— constraint holds. FigureΒ 5.284.1 illustrates this correspondence.

Figure 5.284.1. Correspondence between the partitions associated with collection 〈1,2,6,3,1,2βŒͺ and with collection 〈6,6,2,3,1,3βŒͺ
ctrs/same_partition1
Symmetries
  • Arguments are permutable w.r.t. permutation (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2).

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

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

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

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

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be replaced by any other value that also belongs to the same partition of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚.

Used in

πš”_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—.

See also

implies: 𝚞𝚜𝚎𝚍_πš‹πš’_πš™πšŠπš›πšπš’πšπš’πš˜πš—.

soft variant: 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—_πšŸπšŠπš›Β (variable-based violation measure).

specialisation: πšœπšŠπš–πšŽΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš™πšŠπš›πšπš’πšπš’πš˜πš— replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

system of constraints: πš”_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—.

used in graph description: πš’πš—_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—.

Keywords

characteristic of a constraint: partition.

combinatorial object: permutation.

constraint arguments: constraint between two collections of variables.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš’πš—_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›,π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚)
Graph property(ies)
β€’ for all connected components: ππ’πŽπ”π‘π‚π„=ππ’πˆππŠ
β€’ ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|
β€’ ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.284.2 respectively show the initial and final graph associated with the Example slot. Since we use the ππ’πŽπ”π‘π‚π„ and ππ’πˆππŠ graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint. The πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš— constraint holds since:

  • Each connected component of the final graph has the same number of sources and of sinks.

  • The number of sources of the final graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|.

  • The number of sinks of the final graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|.

Figure 5.284.2. Initial and final graph of the πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš— constraint
ctrs/same_partitionA
(a)
ctrs/same_partitionB
(b)
Signature

Since the initial graph contains only sources and sinks, and since isolated vertices are eliminated from the final graph, we make the following observations:

  • Sources of the initial graph cannot become sinks of the final graph,

  • Sinks of the initial graph cannot become sources of the final graph.

From the previous observations and since we use the π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ arc generator on the collections πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2, we have that the maximum number of sources and sinks of the final graph is respectively equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| and |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|. Therefore we can rewrite ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| to ππ’πŽπ”π‘π‚π„β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| and simplify ππ’πŽπ”π‘π‚π„ Β― Μ² to ππ’πŽπ”π‘π‚π„ Β―. In a similar way, we can rewrite ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| to ππ’πˆππŠβ‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| and simplify ππ’πˆππŠ Β― Μ² to ππ’πˆππŠ Β―.