5.83. cond_lex_less

DESCRIPTIONLINKSAUTOMATON
Origin

Inspired by [WallaceWilson06].

Constraint

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

Type
πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Arguments
πš…π™΄π™²πšƒπ™Ύπš1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™΄π™²πšƒπ™Ύπš2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšžπš™πš•πšŽ-πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚)
Restrictions
|πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚|β‰₯1
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚,πšŸπšŠπš•)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš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
1,0,0,0,πšπšžπš™πš•πšŽ-1,0,πšπšžπš™πš•πšŽ-0,1,πšπšžπš™πš•πšŽ-0,0,πšπšžπš™πš•πšŽ-1,1

The πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœ constraint holds since πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2 are respectively assigned to the first and third 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).

implies: πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš.

Keywords

characteristic of a constraint: vector, automaton.

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint.

filtering: arc-consistency.

modelling: preferences.

symmetry: lexicographic order.

Automaton

FigureΒ 5.83.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.83.2 depicts the reformulation of the πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœ constraint. This reformulation uses:

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

  • The binary constraint 𝙸<𝙹.

Figure 5.83.1. Automaton associated with the preference table of the πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœ constraint given in the Example slot
ctrs/cond_lex_less-1-tikz
Figure 5.83.2. Hypergraph of the reformulation corresponding to the πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœ constraint: it uses two occurrences of the automaton of FigureΒ 5.83.1 and the constraint 𝙸<𝙹
ctrs/cond_lex_less-2-tikz