5.18. among_interval

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŠπš–πš˜πš—πš.

Constraint

πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš•(π™½πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™»π™Ύπš†,πš„π™Ώ)

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

π™½πš…π™°πš is the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ taking a value that is located within interval [π™»π™Ύπš†,πš„π™Ώ].

Example
(3,4,5,8,4,1,3,5)

The πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint holds since we have 3 values, namely 4,5 and 4 that are situated within interval [3,5].

Typical
π™½πš…π™°πš>0
π™½πš…π™°πš<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
π™»π™Ύπš†<πš„π™Ώ
Symmetries
  • 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 [π™»π™Ύπš†,πš„π™Ώ]).

Remark

By giving explicitly all values of the interval [π™»π™Ύπš†,πš„π™Ώ] the πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint can be modelled with the πšŠπš–πš˜πš—πš constraint. However when π™»π™Ύπš†-πš„π™Ώ+1 is a large quantity the πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint provides a more compact form.

See also

generalisation: πšŠπš–πš˜πš—πšΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ in πš’πš—πšπšŽπš›πšŸπšŠπš• replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπšŸπšŠπš•πšžπšŽπšœ).

Keywords

characteristic of a constraint: automaton, automaton with counters.

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

constraint type: value constraint, counting constraint.

filtering: arc-consistency.

modelling: interval.

Arc input(s)

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

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
β€’ π™»π™Ύπš†β‰€πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›β‰€πš„π™Ώ
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½πš…π™°πš

Graph model

The arc constraint corresponds to a unary constraint. For this reason we employ the 𝑆𝐸𝐿𝐹 arc generator in order to produce a graph with a single loop on each vertex.

PartsΒ (A) andΒ (B) of FigureΒ 5.18.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the loops of the final graph are stressed in bold.

Figure 5.18.1. Initial and final graph of the πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/among_intervalActrs/among_intervalB
(a) (b)
Automaton

FigureΒ 5.18.2 depicts the automaton associated with the πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i and πš‚ i : π™»π™Ύπš†β‰€πš…π™°πš i βˆ§πš…π™°πš i β‰€πš„π™Ώβ‡”πš‚ i . The automaton counts the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection that take their value in [π™»π™Ύπš†,πš„π™Ώ] and finally assigns this number to π™½πš…π™°πš.

Figure 5.18.2. Automaton of the πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/among_interval1
Figure 5.18.3. Hypergraph of the reformulation corresponding to the automaton of the πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/among_interval2