5.333. symmetric_gcc

DESCRIPTIONLINKSGRAPH
Origin

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

Constraint

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_𝚐𝚌𝚌(πš…π™°πšπš‚,πš…π™°π™»πš‚)

Synonym

𝚜𝚐𝚌𝚌.

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

Put in relation two sets: for each element of one set gives the corresponding elements of the other set to which it is associated. In addition, enforce a cardinality constraint on the number of occurrences of each value.

Example
πš’πšπšŸπšŠπš›-1πšŸπšŠπš›-{3}πš—πš˜πšŒπšŒ-1,πš’πšπšŸπšŠπš›-2πšŸπšŠπš›-{1}πš—πš˜πšŒπšŒ-1,πš’πšπšŸπšŠπš›-3πšŸπšŠπš›-{1,2}πš—πš˜πšŒπšŒ-2,πš’πšπšŸπšŠπš›-4πšŸπšŠπš›-{1,3}πš—πš˜πšŒπšŒ-2,πš’πšπšŸπšŠπš•-1πšŸπšŠπš•-{2,3,4}πš—πš˜πšŒπšŒ-3,πš’πšπšŸπšŠπš•-2πšŸπšŠπš•-{3}πš—πš˜πšŒπšŒ-1,πš’πšπšŸπšŠπš•-3πšŸπšŠπš•-{1,4}πš—πš˜πšŒπšŒ-2,πš’πšπšŸπšŠπš•-4πšŸπšŠπš•-βˆ…πš—πš˜πšŒπšŒ-0

The πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_𝚐𝚌𝚌 constraint holds since:

  • 3βˆˆπš…π™°πšπš‚[1].πšŸπšŠπš›β‡”1βˆˆπš…π™°π™»πš‚[3].πšŸπšŠπš•,

  • 1βˆˆπš…π™°πšπš‚[2].πšŸπšŠπš›β‡”2βˆˆπš…π™°π™»πš‚[1].πšŸπšŠπš•,

  • 1βˆˆπš…π™°πšπš‚[3].πšŸπšŠπš›β‡”3βˆˆπš…π™°π™»πš‚[1].πšŸπšŠπš•,

  • 2βˆˆπš…π™°πšπš‚[3].πšŸπšŠπš›β‡”3βˆˆπš…π™°π™»πš‚[2].πšŸπšŠπš•,

  • 1βˆˆπš…π™°πšπš‚[4].πšŸπšŠπš›β‡”4βˆˆπš…π™°π™»πš‚[1].πšŸπšŠπš•,

  • 3βˆˆπš…π™°πšπš‚[4].πšŸπšŠπš›β‡”4βˆˆπš…π™°π™»πš‚[3].πšŸπšŠπš•,

  • The number of elements of πš…π™°πšπš‚[1].πšŸπšŠπš›={3} is equal to 1,

  • The number of elements of πš…π™°πšπš‚[2].πšŸπšŠπš›={1} is equal to 1,

  • The number of elements of πš…π™°πšπš‚[3].πšŸπšŠπš›={1,2} is equal to 2,

  • The number of elements of πš…π™°πšπš‚[4].πšŸπšŠπš›={1,3} is equal to 2,

  • The number of elements of πš…π™°π™»πš‚[1].πšŸπšŠπš•={2,3,4} is equal to 3,

  • The number of elements of πš…π™°π™»πš‚[2].πšŸπšŠπš•={3} is equal to 1,

  • The number of elements of πš…π™°π™»πš‚[3].πšŸπšŠπš•={1,4} is equal to 2,

  • The number of elements of πš…π™°π™»πš‚[4].πšŸπšŠπš•=βˆ… is equal to 0.

Symmetries
  • Items of πš…π™°πšπš‚ are permutable.

  • Items of πš…π™°π™»πš‚ are permutable.

Usage

The most simple example of applying πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_𝚐𝚌𝚌 is a variant of personnel assignment problem, where one person can be assigned to perform between n and m (n≀m) jobs, and every job requires between p and q (p≀q) persons. In addition every job requires different kind of skills. The previous problem can be modelled as follows:

  • For each person we create an item of the πš…π™°πšπš‚ collection,

  • For each job we create an item of the πš…π™°π™»πš‚ collection,

  • There is an arc between a person and the particular job if this person is qualified to perform it.

Remark

The πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_𝚐𝚌𝚌 constraint generalises the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint by allowing a variable to take more than one value. It corresponds to a variant of the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint described inΒ [KocjanKreuger04] where the occurrence variables of the πš…π™°πšπš‚ and πš…π™°π™»πš‚ collections are replaced by fixed intervals.

See also

common keyword: πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœΒ (constraint involving set variables).

root concept: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’.

specialisation: πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšπš’πš‘πšŽπš πš’πš—πšπšŽπš›πšŸπšŠπš•).

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

application area: assignment.

combinatorial object: relation.

constraint arguments: constraint involving set variables.

constraint type: decomposition, timetabling constraint.

filtering: flow.

Arc input(s)

πš…π™°πšπš‚ πš…π™°π™»πš‚

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

Arc arity
Arc constraint(s)
β€’ πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πšœ.πš’πšπšŸπšŠπš›,πšŸπšŠπš•πšœ.πšŸπšŠπš•)β‡”πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš•πšœ.πš’πšπšŸπšŠπš•,πšŸπšŠπš›πšœ.πšŸπšŠπš›)
β€’ πšŸπšŠπš›πšœ.πš—πš˜πšŒπšŒ=πšŒπšŠπš›πš_𝚜𝚎𝚝(πšŸπšŠπš›πšœ.πšŸπšŠπš›)
β€’ πšŸπšŠπš•πšœ.πš—πš˜πšŒπšŒ=πšŒπšŠπš›πš_𝚜𝚎𝚝(πšŸπšŠπš•πšœ.πšŸπšŠπš•)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπš‚|*|πš…π™°π™»πš‚|

Graph model

The graph model used for the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_𝚐𝚌𝚌 is similar to the one used in the πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš or in the πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ constraints: we use an equivalence in the arc constraint and ask all arc constraints to hold.

PartsΒ (A) andΒ (B) of FigureΒ 5.333.1 respectively show the initial and final graph. Since we use the 𝐍𝐀𝐑𝐂 graph property, all the arcs of the final graph are stressed in bold.

Figure 5.333.1. Initial and final graph of the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_𝚐𝚌𝚌 constraint
ctrs/symmetric_gccActrs/symmetric_gccB
(a) (b)
Signature

Since we use the π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ arc generator on the collections πš…π™°πšπš‚ and πš…π™°π™»πš‚, the number of arcs of the initial graph is equal to |πš…π™°πšπš‚|Β·|πš…π™°π™»πš‚|. Therefore the maximum number of arcs of the final graph is also equal to |πš…π™°πšπš‚|Β·|πš…π™°π™»πš‚| and we can rewrite 𝐍𝐀𝐑𝐂=|πš…π™°πšπš‚|Β·|πš…π™°π™»πš‚| to 𝐍𝐀𝐑𝐂β‰₯|πš…π™°πšπš‚|Β·|πš…π™°π™»πš‚|. So we can simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.