5.141. element_lesseq

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[OttossonThorsteinssonHooker99]

Constraint

πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš(π™Έπšƒπ™΄π™Ό,πšƒπ™°π™±π™»π™΄)

Arguments
π™Έπšƒπ™΄π™ΌπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπšƒπ™΄π™Ό,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
π™Έπšƒπ™΄π™Ό.πš’πš—πšπšŽπš‘β‰₯1
π™Έπšƒπ™΄π™Ό.πš’πš—πšπšŽπš‘β‰€|πšƒπ™°π™±π™»π™΄|
|π™Έπšƒπ™΄π™Ό|=1
|πšƒπ™°π™±π™»π™΄|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°π™±π™»π™΄,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰₯1
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰€|πšƒπ™°π™±π™»π™΄|
πšπš’πšœπšπš’πš—πšŒπš(πšƒπ™°π™±π™»π™΄,πš’πš—πšπšŽπš‘)
Purpose

π™Έπšƒπ™΄π™Ό[1].πšŸπšŠπš•πšžπšŽ is less than or equal to one of the entries (i.e.,Β the πšŸπšŠπš•πšžπšŽ attribute) of the table πšƒπ™°π™±π™»π™΄.

Example
πš’πš—πšπšŽπš‘-3 πšŸπšŠπš•πšžπšŽ-1,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9

The πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš constraint holds since π™Έπšƒπ™΄π™Ό[1].πšŸπšŠπš•πšžπšŽ=1 is less than or equal to πšƒπ™°π™±π™»π™΄[π™Έπšƒπ™΄π™Ό[1].πš’πš—πšπšŽπš‘].πšŸπšŠπš•πšžπšŽ=πšƒπ™°π™±π™»π™΄[3].πšŸπšŠπš•πšžπšŽ=2.

Typical
|πšƒπ™°π™±π™»π™΄|>1
πš›πšŠπš—πšπšŽ(πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ)>1
Symmetries
  • Items of πšƒπ™°π™±π™»π™΄ are permutable.

  • All occurrences of two distinct values in π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ or πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ can be swapped; all occurrences of a value in π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ or πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ can be renamed to any unused value.

Usage

Used for modelling variable subscripts in linear constraintsΒ [OttossonThorsteinssonHooker99].

Reformulation

By introducing an extra variable πš…π™°π™», the πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš(βŒ©πš’πš—πšπšŽπš‘-π™Έπ™½π™³π™΄πš‡ πšŸπšŠπš•πšžπšŽ-πš…π™°π™»πš„π™΄βŒͺ,πšƒπ™°π™±π™»π™΄) constraint can be expressed in term of an πšŽπš•πšŽπš–(βŒ©πš’πš—πšπšŽπš‘-π™Έπ™½π™³π™΄πš‡ πšŸπšŠπš•πšžπšŽ-πš…π™°π™»βŒͺ,πšƒπ™°π™±π™»π™΄) constraint and of an inequality constraint πš…π™°π™»πš„π™΄β‰€πš…π™°π™».

See also

common keyword: πšŽπš•πšŽπš–πšŽπš—πš, πšŽπš•πšŽπš–πšŽπš—πš_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš, πšŽπš•πšŽπš–πšŽπš—πš_πš™πš›πš˜πšπšžπšŒπšΒ (array constraint).

implied by: πšŽπš•πšŽπš–.

Keywords

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

constraint arguments: binary constraint.

constraint network structure: centered cyclic(2) constraint network(1).

constraint type: data constraint.

filtering: linear programming, arc-consistency.

modelling: array constraint, table, variable subscript, variable indexing.

Cond. implications

πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš(π™Έπšƒπ™΄π™Ό,πšƒπ™°π™±π™»π™΄)

Β Β Β  withΒ  πš–πš’πš—πšŸπšŠπš•(π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ)>0

Β Β Β  andΒ Β  πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ>0

Β Β implies πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš_πšŒπšŠπš™πšŠ(π™±π™Έπ™½πš‚:πšƒπ™°π™±π™»π™΄,π™Έπšƒπ™΄π™Όπš‚:π™Έπšƒπ™΄π™Ό).

Arc input(s)

π™Έπšƒπ™΄π™Ό πšƒπ™°π™±π™»π™΄

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

Arc arity
Arc constraint(s)
β€’ πš’πšπšŽπš–.πš’πš—πšπšŽπš‘=πšπšŠπš‹πš•πšŽ.πš’πš—πšπšŽπš‘
β€’ πš’πšπšŽπš–.πšŸπšŠπš•πšžπšŽβ‰€πšπšŠπš‹πš•πšŽ.πšŸπšŠπš•πšžπšŽ
Graph property(ies)
𝐍𝐀𝐑𝐂=1

Graph model

Similar to the πšŽπš•πšŽπš–πšŽπš—πš constraint except that the equality constraint of the second condition of the arc constraint is replaced by a less than or equal to constraint.

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

Figure 5.141.1. Initial and final graph of the πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš constraint
ctrs/element_lesseqActrs/element_lesseqB
(a) (b)
Signature

Since all the πš’πš—πšπšŽπš‘ attributes of πšƒπ™°π™±π™»π™΄ are distinct and because of the first arc constraint the final graph cannot have more than one arc. Therefore we can rewrite 𝐍𝐀𝐑𝐂=1 to 𝐍𝐀𝐑𝐂β‰₯1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

Automaton

FigureΒ 5.141.2 depicts the automaton associated with the πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš constraint. Let π™Έπ™½π™³π™΄πš‡ and πš…π™°π™»πš„π™΄ respectively be the πš’πš—πšπšŽπš‘ and the πšŸπšŠπš•πšžπšŽ attributes of the unique item of the π™Έπšƒπ™΄π™Ό collection. Let π™Έπ™½π™³π™΄πš‡ i and πš…π™°π™»πš„π™΄ i respectively be the πš’πš—πšπšŽπš‘ and the πšŸπšŠπš•πšžπšŽ attributes of the i th item of the πšƒπ™°π™±π™»π™΄ collection. To each quadruple (π™Έπ™½π™³π™΄πš‡,πš…π™°π™»πš„π™΄,π™Έπ™½π™³π™΄πš‡ i ,πš…π™°π™»πš„π™΄ i ) corresponds a 0-1 signature variable S i as well as the following signature constraint: ((π™Έπ™½π™³π™΄πš‡=π™Έπ™½π™³π™΄πš‡ i )∧(πš…π™°π™»πš„π™΄β‰€πš…π™°π™»πš„π™΄ i ))⇔S i .

Figure 5.141.2. Automaton of the πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš constraint
ctrs/element_lesseq-1-tikz
Figure 5.141.3. Hypergraph of the reformulation corresponding to the automaton of the πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš constraint
ctrs/element_lesseq-2-tikz