5.25. arith_or

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Used in the definition of several automata

Constraint

πšŠπš›πš’πšπš‘_πš˜πš›(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšπ™΄π™»π™Ύπ™Ώ,πš…π™°π™»πš„π™΄)

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πšπ™΄π™»π™Ύπ™ΏπšŠπšπš˜πš–
πš…π™°π™»πš„π™΄πš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|
πšπ™΄π™»π™Ύπ™Ώβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

Enforce for all pairs of variables πšŸπšŠπš›1 i ,πšŸπšŠπš›2 i of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections to have πšŸπšŠπš›1 i πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄βˆ¨πšŸπšŠπš›2 i πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄.

Example
0,1,0,0,1,0,0,0,1,0,=,0

The constraint πšŠπš›πš’πšπš‘_πš˜πš› holds since, for all pairs of variables πšŸπšŠπš›1 i ,πšŸπšŠπš›2 i of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections, there is at least one variable that is equal to 0.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|>0
Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are permutable (same permutation used).

See also

specialisation: πšŠπš›πš’πšπš‘Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄ ∨ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄).

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint network structure: Berge-acyclic constraint network.

constraint type: decomposition, value constraint.

filtering: arc-consistency.

final graph structure: acyclic, bipartite, no loop.

modelling: disjunction.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš› πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄βˆ¨πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš› πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|

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

Graph model

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

Figure 5.25.1. Initial and final graph of the πšŠπš›πš’πšπš‘_πš˜πš› constraint
ctrs/arith_orActrs/arith_orB
(a) (b)
Automaton

FigureΒ 5.25.2 depicts the automaton associated with the πšŠπš›πš’πšπš‘_πš˜πš› constraint. Let πš…π™°πš1 i and πš…π™°πš2 i be the i th variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections. To each pair of variables (πš…π™°πš1 i ,πš…π™°πš2 i ) corresponds a signature variable πš‚ i . The following signature constraint links πš…π™°πš1 i , πš…π™°πš2 i and πš‚ i : πš…π™°πš1 i πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄βˆ¨πš…π™°πš2 i πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄β‡”πš‚ i . The automaton enforces for each pair of variables πš…π™°πš1 i ,πš…π™°πš2 i the condition πš…π™°πš1 i πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄βˆ¨πš…π™°πš2 i πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄.

Figure 5.25.2. Automaton of the πšŠπš›πš’πšπš‘_πš˜πš› constraint
ctrs/arith_or1
Figure 5.25.3. Hypergraph of the reformulation corresponding to the automaton of the πšŠπš›πš’πšπš‘_πš˜πš› constraint
ctrs/arith_or2