5.173. group_skip_isolated_item

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšπš›πš˜πšžπš™.

Constraint

πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš–π™½π™Άπšπ™Ύπš„π™Ώ,𝙼𝙸𝙽_πš‚π™Έπš‰π™΄,π™Όπ™°πš‡_πš‚π™Έπš‰π™΄,π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚

Arguments
π™½π™Άπšπ™Ύπš„π™ΏπšπšŸπšŠπš›
𝙼𝙸𝙽_πš‚π™Έπš‰π™΄πšπšŸπšŠπš›
π™Όπ™°πš‡_πš‚π™Έπš‰π™΄πšπšŸπšŠπš›
π™½πš…π™°π™»πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Restrictions
π™½π™Άπšπ™Ύπš„π™Ώβ‰₯0
3*π™½π™Άπšπ™Ύπš„π™Ώβ‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|+1
𝙼𝙸𝙽_πš‚π™Έπš‰π™΄β‰₯0
𝙼𝙸𝙽_πš‚π™Έπš‰π™΄β‰ 1
π™Όπ™°πš‡_πš‚π™Έπš‰π™΄β‰₯𝙼𝙸𝙽_πš‚π™Έπš‰π™΄
π™½πš…π™°π™»β‰₯π™Όπ™°πš‡_πš‚π™Έπš‰π™΄
π™½πš…π™°π™»β‰₯π™½π™Άπšπ™Ύπš„π™Ώ
π™½πš…π™°π™»β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
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 the following conditions 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,

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

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

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

Example
(1,2,2,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), and the fact that isolated even values are ignored, the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint holds since:

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

  • Its second and third arguments, 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ and π™Όπ™°πš‡_πš‚π™Έπš‰π™΄, are both set to 2 since the only group of even values with more than one even value involves two values (i.e.,Β group 2 8).

  • The fourth argument, π™½πš…π™°π™», is fixed to 2 since it corresponds to the total number of even values belonging to groups involving more than one even value (i.e.,Β value 4 is discarded since it is an isolated even value of the sequence 2 8 1 7 4 5 1 1 1).

Typical
π™½π™Άπšπ™Ύπš„π™Ώ>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 πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•).

Arg. properties
  • Functional dependency: π™½π™Άπšπ™Ύπš„π™Ώ determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and πš…π™°π™»πš„π™΄πš‚.

  • Functional dependency: 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and πš…π™°π™»πš„π™΄πš‚.

  • Functional dependency: π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and πš…π™°π™»πš„π™΄πš‚.

  • Functional dependency: π™½πš…π™°π™» determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and πš…π™°π™»πš„π™΄πš‚.

Usage

This constraint is useful in order to specify rules about how rest days should be allocated to a person during a period of n consecutive days. In this case πš…π™°π™»πš„π™΄πš‚ are the codes for the rest days (perhaps a single value) and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds to the amount of work done during n consecutive days. We can then express a rule like: in a month one should have at least 4 periods of at least 2 rest days (isolated rest days are not counted as rest periods).

Remark

The following invariant imposes a limit on the maximum number of groups wrt the minimum size of a group and the total number of variables: π™½π™Άπšπ™Ύπš„π™ΏΒ·(max(𝙼𝙸𝙽_πš‚π™Έπš‰π™΄,2)+1)≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|+1.

See also

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

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

Keywords

characteristic of a constraint: automaton, automaton with counters, automaton with same input symbol.

combinatorial object: sequence.

constraint arguments: reverse of a constraint.

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

constraint type: timetabling constraint.

filtering: glue matrix.

final graph structure: strongly connected component.

modelling: functional dependency.

Arc input(s)

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

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

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

Graph model

We use the 𝐢𝐻𝐴𝐼𝑁 arc generator in order to produce the initial graph. In the context of the Example slot, this creates the graph depicted in partΒ (A) of FigureΒ 5.173.1. We use 𝐢𝐻𝐴𝐼𝑁 together with the arc constraint πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›βˆˆπš…π™°π™»πš„π™΄πš‚βˆ§πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›βˆˆπš…π™°π™»πš„π™΄πš‚ in order to skip the isolated variables that take a value in πš…π™°π™»πš„π™΄πš‚ that we do not want to count as a group. This is why, on the example, value 4 is not counted as a group. PartΒ (B) of FigureΒ 5.173.1 shows the final graph associated with the Example slot. The πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint of the Example slot holds since:

  • The final graph contains one strongly connected component. Therefore the number of groups is equal to one.

  • The unique strongly connected component of the final graph contains two vertices. Therefore 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ and π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ are both equal to 2.

  • The number of vertices of the final graph is equal to two. Therefore π™½πš…π™°π™» is equal to 2.

Figure 5.173.1. Initial and final graph of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint
ctrs/group_skip_isolated_itemActrs/group_skip_isolated_itemB
(a) (b)
Automaton

FiguresΒ 5.173.2,Β 5.173.4,Β 5.173.6 andΒ 5.173.8 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.173.2. Automaton for the π™½π™Άπšπ™Ύπš„π™Ώ argument of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint and its glue matrix
ctrs/group_skip_isolated_item-1-tikz
Figure 5.173.3. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the π™½π™Άπšπ™Ύπš„π™Ώ argument of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint (since all states of the automaton are accepting there is no restriction on the last variable Q n )
ctrs/group_skip_isolated_item-2-tikz
Figure 5.173.4. Automaton for the 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ argument of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint and its glue matrix
ctrs/group_skip_isolated_item-3-tikz
Figure 5.173.5. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ argument of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint where 𝙽 stands for |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| (since all states of the automaton are accepting there is no restriction on the last variable Q n )
ctrs/group_skip_isolated_item-4-tikz
Figure 5.173.6. Automaton for the π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ argument of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint and its glue matrix
ctrs/group_skip_isolated_item-5-tikz
Figure 5.173.7. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the π™Όπ™°πš‡_πš‚π™Έπš‰π™΄ argument of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint (since all states of the automaton are accepting there is no restriction on the last variable Q n )
ctrs/group_skip_isolated_item-6-tikz
Figure 5.173.8. Automaton for the π™½πš…π™°π™» argument of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint and its glue matrix
ctrs/group_skip_isolated_item-7-tikz
Figure 5.173.9. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the π™½πš…π™°π™» argument of the πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš– constraint
ctrs/group_skip_isolated_item-8-tikz