5.292. sliding_card_skip0

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

N.Β Beldiceanu

Constraint

πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0(π™°πšƒπ™»π™΄π™°πš‚πšƒ,π™°πšƒπ™Όπ™Ύπš‚πšƒ,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

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

Let n be the total number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. A maximum non-zero set of consecutive variables X i ..X j (1≀i≀j≀n) is defined in the following way:

  • All variables X i ,...,X j take a non-zero value,

  • i=1 or X i-1 is equal to 0,

  • j=n or X j+1 is equal to 0.

Enforces that each maximum non -zero set of consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ contains at least π™°πšƒπ™»π™΄π™°πš‚πšƒ and at most π™°πšƒπ™Όπ™Ύπš‚πšƒ values from the collection of values πš…π™°π™»πš„π™΄πš‚.

Example
2,3,πšŸπšŠπš›-0,πšŸπšŠπš›-7,πšŸπšŠπš›-2,πšŸπšŠπš›-9,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-9,πšŸπšŠπš›-4,πšŸπšŠπš›-9,7,9

The πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0 constraint holds since the two maximum non -zero set of consecutive values 7 2 9 and 9 4 9 of its third argument 〈0,7,2,9,0,0,9,4,9βŒͺ take both 2 (2∈[π™°πšƒπ™»π™΄π™°πš‚πšƒ,π™°πšƒπ™Όπ™Ύπš‚πšƒ]=[2,3]) values within the set of values 〈7,9βŒͺ.

Symmetries
  • π™°πšƒπ™»π™΄π™°πš‚πšƒ can be decreased to any value β‰₯0.

  • π™°πšƒπ™Όπ™Ύπš‚πšƒ can be increased to any value ≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

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

Usage

This constraint is useful in timetabling problems where the variables are interpreted as the type of job that a person does on consecutive days. Value 0 represents a rest day and one imposes a cardinality constraint on periods that are located between rest periods.

Remark

One cannot initially state a πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint since the rest days are not yet allocated. One can also not use an πšŠπš–πš˜πš—πš_𝚜𝚎𝚚 constraint since it does not hold for the sequences of consecutive variables that contains at least one rest day.

See also

related: πšŠπš–πš˜πš—πšΒ (counting constraint on the full sequence), πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (counting constraint for different values on the full sequence).

specialisation: πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™Β (maximal sequences replaced by the full sequence).

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

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

constraint type: timetabling constraint, sliding sequence constraint.

miscellaneous: obscure.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›β‰ 0
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›β‰ 0
Sets
𝖒𝖒↦[πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ]

Constraint(s) on sets
πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™(π™°πšƒπ™»π™΄π™°πš‚πšƒ,π™°πšƒπ™Όπ™Ύπš‚πšƒ,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,πš…π™°π™»πš„π™΄πš‚)
Graph model

Note that the arc constraint will produce the different sequences of consecutive variables that do not contain any 0. The 𝖒𝖒 set generator produces all the connected components of the final graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.292.1 respectively show the initial and final graph associated with the Example slot. Since we use the set generator 𝖒𝖒 we show the two connected components of the final graph. Since these two connected components both contains between 2 and 3 variables that take their values in {7,9} the πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0 constraint holds.

Figure 5.292.1. Initial and final graph of the πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0 constraint
ctrs/sliding_card_skip0Actrs/sliding_card_skip0B
(a) (b)
Automaton

FigureΒ 5.292.2 depicts the automaton associated with the πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0 constraint. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i . The following signature constraint links πš…π™°πš i and πš‚ i :

(πš…π™°πš i =0)β‡”πš‚ i =0 ∧

(πš…π™°πš i β‰ 0βˆ§πš…π™°πš i βˆ‰πš…π™°π™»πš„π™΄πš‚)β‡”πš‚ i =1 ∧

(πš…π™°πš i β‰ 0βˆ§πš…π™°πš i βˆˆπš…π™°π™»πš„π™΄πš‚)β‡”πš‚ i =2.

Figure 5.292.2. Automaton of the πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0 constraint
ctrs/sliding_card_skip01
Figure 5.292.3. Hypergraph of the reformulation corresponding to the automaton of the πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0 constraint
ctrs/sliding_card_skip02