5.19. among_low_up

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[BeldiceanuContejean94]

Constraint

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

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

Between π™»π™Ύπš† and πš„π™Ώ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection are assigned a value of the πš…π™°π™»πš„π™΄πš‚ collection.

Example
1,2,9,2,4,5,0,2,4,6,8

The πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™ constraint holds since between 1 and 2 values (i.e.,Β in fact 2 values) of the collection of values 〈9,2,4,5βŒͺ belong to the set of values {0,2,4,6,8}.

Typical
π™»π™Ύπš†<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš„π™Ώ>0
π™»π™Ύπš†<πš„π™Ώ
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
|πš…π™°π™»πš„π™΄πš‚|>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

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

  • π™»π™Ύπš† can be decreased to any value β‰₯0.

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

  • 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 πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•).

Algorithm

The πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™ constraint is entailed if and only if the following two conditions hold:

  1. The number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection assigned a value of the πš…π™°π™»πš„π™΄πš‚ collection is greater than or equal to π™»π™Ύπš†.

  2. The number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection that can potentially be assigned a value of the πš…π™°π™»πš„π™΄πš‚ collection is less than or equal to πš„π™Ώ.

Used in

πšŠπš–πš˜πš—πš_𝚜𝚎𝚚, πšŒπš’πšŒπš•πšŽ_πšŒπšŠπš›πš_πš˜πš—_πš™πšŠπšπš‘, πš’πš—πšπšŽπš›πšŸπšŠπš•_πšŠπš—πš_πšŒπš˜πšžπš—πš, πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0.

See also

assignment dimension added: πš’πš—πšπšŽπš›πšŸπšŠπš•_πšŠπš—πš_πšŒπš˜πšžπš—πšΒ (assignment dimension corresponding to intervals added).

generalisation: πšŠπš–πš˜πš—πšΒ (πš’πš—πšπšŽπš›πšŸπšŠπš• replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ), πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0Β (full sequence replaced by maximal sequences of non -zeros).

system of constraints: πšŠπš–πš˜πš—πš_𝚜𝚎𝚚.

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.

final graph structure: acyclic, bipartite, no loop.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•
Graph property(ies)
β€’ 𝐍𝐀𝐑𝐂β‰₯π™»π™Ύπš†
β€’ ππ€π‘π‚β‰€πš„π™Ώ

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Each arc constraint of the final graph corresponds to the fact that a variable is assigned to a value that belong to the πš…π™°π™»πš„π™΄πš‚ collection. The two graph properties restrict the total number of arcs to the interval [π™»π™Ύπš†,πš„π™Ώ].

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

Figure 5.19.1. Initial and final graph of the πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™ constraint
ctrs/among_low_upActrs/among_low_upB
(a) (b)
Automaton

FigureΒ 5.19.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 . The automaton counts the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection that take their value in πš…π™°π™»πš„π™΄πš‚ and finally checks that this number is within the interval [π™»π™Ύπš†,πš„π™Ώ].

Figure 5.19.2. Automaton of the πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™ constraint
ctrs/among_low_up1
Figure 5.19.3. Hypergraph of the reformulation corresponding to the automaton of the πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™ constraint
ctrs/among_low_up2