5.147. group

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHIP

Constraint

πšπš›πš˜πšžπš™π™½π™Άπšπ™Ύπš„π™Ώ,𝙼𝙸𝙽_πš‚π™Έπš‰π™΄,π™Όπ™°πš‡_πš‚π™Έπš‰π™΄,𝙼𝙸𝙽_π™³π™Έπš‚πšƒ,π™Όπ™°πš‡_π™³π™Έπš‚πšƒ,π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚

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

Let n be the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Let X i ,X i+1 ,...,X j (1≀i≀j≀n) be consecutive variables of the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ such that all the following conditions simultaneously apply:

  • All variables X i ,...,X j take their value in the set of values πš…π™°π™»πš„π™΄πš‚,

  • i=1 or X i-1 does not take a value in πš…π™°π™»πš„π™΄πš‚,

  • j=n or X j+1 does not take a value in πš…π™°π™»πš„π™΄πš‚.

We call such a set of variables a group. The constraint πšπš›πš˜πšžπš™ is true if all the following conditions hold:

  • There are exactly π™½π™Άπšπ™Ύπš„π™Ώ groups of variables,

  • 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ is the number of variables of the smallest group,

  • π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ is the number of variables of the largest group,

  • 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ is the minimum number of variables between two consecutive groups or between one border and one group,

  • π™Όπ™°πš‡_π™³π™Έπš‚πšƒ is the maximum number of variables between two consecutive groups or between one border and one group,

  • π™½πš…π™°π™» is the number of variables that take their value in the set of values πš…π™°π™»πš„π™΄πš‚.

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

Given the fact that groups are formed by even values in {0,2,4,6,8} (i.e.,Β values expressed by the πš…π™°π™»πš„π™΄πš‚ collection), the πšπš›πš˜πšžπš™ constraint holds since:

  • Its first argument, π™½π™Άπšπ™Ύπš„π™Ώ, is set to value 2 since the sequence 2 8 1 7 4 5 1 1 1 contains two groups of even values (i.e.,Β group 2 8 and groupΒ 4).

  • Its second argument, 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄, is set to value 1 since the smallest group of even values involves only one single value (i.e.,Β valueΒ 4).

  • Its third argument, π™Όπ™°πš‡_πš‚π™Έπš‰π™΄, is set to value 2 since the largest group of even values involves two values (i.e.,Β group 2 8).

  • Its fourth argument, 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ, is set to value 2 since the smallest group of odd values involves two values (i.e.,Β group 1 7).

  • Its fifth argument, π™Όπ™°πš‡_π™³π™Έπš‚πšƒ, is set to value 4 since the largest group of odd values involves four values (i.e.,Β group 5 1 1 1).

  • Its sixth argument, π™½πš…π™°π™», is set to value 3 since the total number of even values of the sequence 2 8 1 7 4 5 1 1 1 is equal to 3 (i.e.,Β values 2, 8 and 4).

Typical
π™½π™Άπšπ™Ύπš„π™Ώ>0
𝙼𝙸𝙽_πš‚π™Έπš‰π™΄>0
π™Όπ™°πš‡_πš‚π™Έπš‰π™΄>𝙼𝙸𝙽_πš‚π™Έπš‰π™΄
𝙼𝙸𝙽_π™³π™Έπš‚πšƒ>0
π™Όπ™°πš‡_π™³π™Έπš‚πšƒ>𝙼𝙸𝙽_π™³π™Έπš‚πšƒ
π™Όπ™°πš‡_π™³π™Έπš‚πšƒ<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
π™½πš…π™°π™»>π™Όπ™°πš‡_πš‚π™Έπš‰π™΄
π™½πš…π™°π™»>π™½π™Άπšπ™Ύπš„π™Ώ
π™½πš…π™°π™»<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
|πš…π™°π™»πš„π™΄πš‚|>0
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

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

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that belongs to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. does not belong to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•) can be replaced by any other value in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. not in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•).

Usage

A typical use of the πšπš›πš˜πšžπš™ constraint in the context of timetabling is as follow: The value of the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection corresponds to the type of shift (i.e.,Β night, morning, afternoon, rest) performed by a specific person on day i. A complete period of work is represented by the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. In this context the πšπš›πš˜πšžπš™ constraint expresses for a person:

  • The number of periods of consecutive night -shift during a complete period of work.

  • The total number of night -shift during a complete period of work.

  • The maximum number of allowed consecutive night -shift.

  • The minimum number of days, which do not correspond to a night -shift, between two consecutive sequences of night -shift.

Remark

For this constraint we use the possibility to express directly more than one constraint on the parameters of the final graph we want to obtain. For more propagation, it is crucial to keep this in one single constraint, since strong relations relate the different parameters of a graph. This constraint is very similar to the πšπš›πš˜πšžπš™ constraint introduced in CHIP, except that here, the 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ and π™Όπ™°πš‡_π™³π™Έπš‚πšƒ constraints apply also for the two borders: we cannot start or end with a group of k consecutive variables that take their values outside πš…π™°π™»πš„π™΄πš‚ and such that k is less than 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ or k is greater than π™Όπ™°πš‡_π™³π™Έπš‚πšƒ.

See also

common keyword: πšŒπš‘πšŠπš—πšπšŽ_πšŒπš˜πš—πšπš’πš—πšžπš’πšπš’Β (timetabling constraint,sequence),

πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’Β (sequence),

πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš–Β (timetabling constraint,sequence),

πš™πšŠπšπšπšŽπš›πš—, πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πšΒ (timetabling constraint),

πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘Β (timetabling constraint,sequence).

shift of concept: πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ.

used in graph description: πš’πš—, πš—πš˜πš_πš’πš—.

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

constraint network structure: alpha-acyclic constraint network(2), alpha-acyclic constraint network(3).

constraint type: timetabling constraint.

final graph structure: connected component, vpartition, consecutive loops are connected.

miscellaneous: obscure.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
β€’ πš’πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›,πš…π™°π™»πš„π™΄πš‚)
β€’ πš’πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›,πš…π™°π™»πš„π™΄πš‚)
Graph property(ies)
β€’ 𝐍𝐂𝐂=π™½π™Άπšπ™Ύπš„π™Ώ
β€’ 𝐌𝐈𝐍_𝐍𝐂𝐂=𝙼𝙸𝙽_πš‚π™Έπš‰π™΄
β€’ πŒπ€π—_𝐍𝐂𝐂=π™Όπ™°πš‡_πš‚π™Έπš‰π™΄
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=π™½πš…π™°π™»

Arc input(s)

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

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

Arc arity
Arc constraint(s)
β€’ πš—πš˜πš_πš’πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›,πš…π™°π™»πš„π™΄πš‚)
β€’ πš—πš˜πš_πš’πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›,πš…π™°π™»πš„π™΄πš‚)
Graph property(ies)
β€’ 𝐌𝐈𝐍_𝐍𝐂𝐂=𝙼𝙸𝙽_π™³π™Έπš‚πšƒ
β€’ πŒπ€π—_𝐍𝐂𝐂=π™Όπ™°πš‡_π™³π™Έπš‚πšƒ

Graph model

We use two graph constraints for modelling the πšπš›πš˜πšžπš™ constraint: a first one for specifying the constraints on π™½π™Άπšπ™Ύπš„π™Ώ, 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄, π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ and π™½πš…π™°π™», and a second one for stating the constraints on 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ and π™Όπ™°πš‡_π™³π™Έπš‚πšƒ. In order to generate the initial graph related to the first graph constraint we use:

  • The arc generators 𝑃𝐴𝑇𝐻 and 𝐿𝑂𝑂𝑃,

  • The binary constraint πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›βˆˆπš…π™°π™»πš„π™΄πš‚βˆ§πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›βˆˆπš…π™°π™»πš„π™΄πš‚.

On the first graph constraint of the Example slot this produces an initial graph depicted in partΒ (A) of FigureΒ 5.147.1. We use 𝑃𝐴𝑇𝐻 𝐿𝑂𝑂𝑃 and the binary constraint πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›βˆˆπš…π™°π™»πš„π™΄πš‚βˆ§πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›βˆˆπš…π™°π™»πš„π™΄πš‚ in order to catch the two following situations:

  • A binary constraint has to be used in order to get the notion of group: Consecutive variables that take their value in πš…π™°π™»πš„π™΄πš‚.

  • If we only use 𝑃𝐴𝑇𝐻 then we would lose the groups that are composed from one single variable since the predecessor and the successor arc would be destroyed; this is why we use also the 𝐿𝑂𝑂𝑃 arc generator.

PartΒ (B) of FigureΒ 5.147.1 shows the final graph associated with the first graph constraint of the Example slot. Since we use the 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 graph property, the vertices of the final graph are stressed in bold. In addition, since we use the 𝐌𝐈𝐍_𝐍𝐂𝐂 and the πŒπ€π—_𝐍𝐂𝐂 graph properties, we also show the smallest and largest connected components of the final graph.

Figure 5.147.1. Initial and final graph of the πšπš›πš˜πšžπš™ constraint
ctrs/groupActrs/groupB
(a) (b)

The πšπš›πš˜πšžπš™ constraint of the Example slot holds since:

  • The final graph of the first graph constraint has two connected components. Therefore the number of groups π™½π™Άπšπ™Ύπš„π™Ώ is equal to two.

  • The number of vertices of the smallest connected component of the final graph of the first graph constraint is equal to 1. Therefore 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ is equal to 1.

  • The number of vertices of the largest connected component of the final graph of the first graph constraint is equal to 2. Therefore π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ is equal to 2.

  • The number of vertices of the smallest connected component of the final graph of the second graph constraint is equal to 2. Therefore 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ is equal to 2.

  • The number of vertices of the largest connected component of the final graph of the second graph constraint is equal to 4. Therefore π™Όπ™°πš‡_π™³π™Έπš‚πšƒ is equal to 4.

  • The number of vertices of the final graph of the first graph constraint is equal to three. Therefore π™½πš…π™°π™» is equal to 3.

Automaton

FiguresΒ 5.147.2,Β 5.147.4,Β 5.147.5,Β 5.147.7,Β 5.147.8 andΒ 5.147.10 depict the different automata associated with the πšπš›πš˜πšžπš™ constraint. For the automata that respectively compute π™½π™Άπšπ™Ύπš„π™Ώ, 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄, π™Όπ™°πš‡_πš‚π™Έπš‰π™΄, 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ, π™Όπ™°πš‡_π™³π™Έπš‚πšƒ and π™½πš…π™°π™» we have a 0-1 signature variable πš‚ i for each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. The following signature constraint links πš…π™°πš i and πš‚ i : πš…π™°πš i βˆˆπš…π™°π™»πš„π™΄πš‚β‡”πš‚ i .

Figure 5.147.2. Automaton for the π™½π™Άπšπ™Ύπš„π™Ώ parameter of the πšπš›πš˜πšžπš™ constraint
ctrs/group1
Figure 5.147.3. Hypergraph of the reformulation corresponding to the automaton of the π™½π™Άπšπ™Ύπš„π™Ώ parameter of the πšπš›πš˜πšžπš™ constraint
ctrs/group2
Figure 5.147.4. Automaton for the 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ parameter of the πšπš›πš˜πšžπš™ constraint
ctrs/group31
Figure 5.147.5. Automaton for the π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ parameter of the πšπš›πš˜πšžπš™ constraint
ctrs/group32
Figure 5.147.6. Hypergraphs of the reformulations corresponding to the automata of the 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ and π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ parameters of the πšπš›πš˜πšžπš™ constraint
ctrs/group4
Figure 5.147.7. Automaton for the 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ parameter of the πšπš›πš˜πšžπš™ constraint
ctrs/group51
Figure 5.147.8. Automaton for the π™Όπ™°πš‡_π™³π™Έπš‚πšƒ parameter of the πšπš›πš˜πšžπš™ constraint
ctrs/group52
Figure 5.147.9. Hypergraphs of the reformulations corresponding to the automata of the 𝙼𝙸𝙽_π™³π™Έπš‚πšƒ and π™Όπ™°πš‡_π™³π™Έπš‚πšƒ parameters of the πšπš›πš˜πšžπš™ constraint
ctrs/group6
Figure 5.147.10. Automaton for the π™½πš…π™°π™» parameter of the πšπš›πš˜πšžπš™ constraint
ctrs/group7
Figure 5.147.11. Hypergraph of the reformulation corresponding to the automaton of the π™½πš…π™°π™» parameter of the πšπš›πš˜πšžπš™ constraint
ctrs/group8