5.201. lex_lesseq_allperm

DESCRIPTIONLINKS
Origin

Inspired by [FlenerFrischHnichKiziltanMiguelPearsonWalsh02]

Constraint

πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš_πšŠπš•πš•πš™πšŽπš›πš–(πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2)

Synonym

πš•πšŽπš‘πš’πš–πš’πš—.

Arguments
πš…π™΄π™²πšƒπ™Ύπš1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™΄π™²πšƒπ™Ύπš2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš2,πšŸπšŠπš›)
|πš…π™΄π™²πšƒπ™Ύπš1|=|πš…π™΄π™²πšƒπ™Ύπš2|
Purpose

πš…π™΄π™²πšƒπ™Ύπš1 is lexicographically less than or equal to all permutations of πš…π™΄π™²πšƒπ™Ύπš2. Given two vectors, X β†’ and Y β†’ of n components, 〈X 0 ,...,X n-1 βŒͺ and 〈Y 0 ,...,Y n-1 βŒͺ, X β†’ is lexicographically less than or equal to Y β†’ if and only if n=0 or X 0 <Y 0 or X 0 =Y 0 and 〈X 1 ,...,X n-1 βŒͺ is lexicographically less than or equal to 〈Y 1 ,...,Y n-1 βŒͺ.

Example
1,2,3,3,1,2

The πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš_πšŠπš•πš•πš™πšŽπš›πš– constraint holds since vector 〈1,2,3βŒͺ is lexicographically less than or equal to all the permutations of vector 〈3,1,2βŒͺ (i.e., 〈1,2,3βŒͺ, 〈1,3,2βŒͺ, 〈2,1,3βŒͺ, 〈2,3,1βŒͺ, 〈3,1,2βŒͺ, 〈3,2,1βŒͺ).

Symmetry

All occurrences of two distinct values in πš…π™΄π™²πšƒπ™Ύπš1.πšŸπšŠπš› or πš…π™΄π™²πšƒπ™Ύπš2.πšŸπšŠπš› can be swapped; all occurrences of a value in πš…π™΄π™²πšƒπ™Ύπš1.πšŸπšŠπš› or πš…π™΄π™²πšƒπ™Ύπš2.πšŸπšŠπš› can be renamed to any unused value.

Remark

The πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš_πšŠπš•πš•πš™πšŽπš›πš–(πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2) can be reformulated as the conjunction πšœπš˜πš›πš(πš…π™΄π™²πšƒπ™Ύπš2,πš…π™΄π™²πšƒπ™Ύπš), πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš(πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš).

Systems

leximin in Choco.

Used in

πšŠπš•πš•πš™πšŽπš›πš–.

See also

common keyword: πšŠπš•πš•πš™πšŽπš›πš–Β (matrix symmetry,lexicographic order).

implies: πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš.

system of constraints: πšŠπš•πš•πš™πšŽπš›πš–.

Keywords

characteristic of a constraint: vector.

constraint type: predefined constraint, order constraint.

symmetry: symmetry, matrix symmetry, lexicographic order.