5.68. cond_lex_greatereq

DESCRIPTIONLINKSAUTOMATON
Origin

Inspired by [WallaceWilson06].

Constraint

πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš(πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2,π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄)

Type
πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Arguments
πš…π™΄π™²πšƒπ™Ύπš1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™΄π™²πšƒπ™Ύπš2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšžπš™πš•πšŽ-πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚,πšŸπšŠπš•)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš2,πšŸπšŠπš›)
|πš…π™΄π™²πšƒπ™Ύπš1|=|πš…π™΄π™²πšƒπ™Ύπš2|
|πš…π™΄π™²πšƒπ™Ύπš1|=|πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄,πšπšžπš™πš•πšŽ)
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄,πšπšžπš™πš•πšŽ)
πšπš’πšœπšπš’πš—πšŒπš(π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄,[])
πš’πš—_πš›πšŽπš•πšŠπšπš’πš˜πš—(πš…π™΄π™²πšƒπ™Ύπš1,π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄)
πš’πš—_πš›πšŽπš•πšŠπšπš’πš˜πš—(πš…π™΄π™²πšƒπ™Ύπš2,π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄)
Purpose

πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2 are both assigned to the 𝙸 th and 𝙹 th items of the collection π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄ such that 𝙸β‰₯𝙹.

Example
0,0,1,0,πšπšžπš™πš•πšŽ-1,0,πšπšžπš™πš•πšŽ-0,1,πšπšžπš™πš•πšŽ-0,0,πšπšžπš™πš•πšŽ-1,1

The πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš constraint holds since πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2 are respectively assigned to the third and first items of the collection π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.

Typical
|πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚|>1
|πš…π™΄π™²πšƒπ™Ύπš1|>1
|πš…π™΄π™²πšƒπ™Ύπš2|>1
|π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄|>1
Symmetries
  • Items of πš…π™΄π™²πšƒπ™Ύπš1, πš…π™΄π™²πšƒπ™Ύπš2 and π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.πšπšžπš™πš•πšŽ are permutable (same permutation used).

  • All occurrences of two distinct tuples of values in πš…π™΄π™²πšƒπ™Ύπš1, πš…π™΄π™²πšƒπ™Ύπš2 or π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.πšπšžπš™πš•πšŽ can be swapped; all occurrences of a tuple of values in πš…π™΄π™²πšƒπ™Ύπš1, πš…π™΄π™²πšƒπ™Ύπš2 or π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.πšπšžπš™πš•πšŽ can be renamed to any unused tuple of values.

Usage

See πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝.

See also

common keyword: πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝, πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›, πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœ, πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπššΒ (preferences), πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπššΒ (lexicographic order).

implied by: πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›.

Keywords

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

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint.

filtering: arc-consistency.

modelling: preferences.

symmetry: lexicographic order.

Automaton

FigureΒ 5.68.1 depicts the automaton associated with the preference table of the πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš constraint given in the example. Let πš…π™°πš1 k and πš…π™°πš2 k respectively be the πšŸπšŠπš› attributes of the k th items of the πš…π™΄π™²πšƒπ™Ύπš1 and the πš…π™΄π™²πšƒπ™Ύπš2 collections. FigureΒ 5.68.2 depicts the reformulation of the πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš constraint. This reformulation uses:

  • Two occurrences of the automaton depicted by FigureΒ 5.68.1 for computing the positions 𝙸 and 𝙹 within the preference table corresponding to πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2.

  • The binary constraint 𝙸β‰₯𝙹.

Figure 5.68.1. Automaton associated with the preference table of the πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš constraint given in the example
ctrs/cond_lex_greatereq1
Figure 5.68.2. Hypergraph of the reformulation corresponding to the πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš constraint: it uses two occurrences of the automaton of FigureΒ 5.68.1 and the constraint 𝙸β‰₯𝙹
ctrs/cond_lex_greatereq2