Global Constraint Catalog: Clex_lesseq

5.233. lex_lesseq_allperm

DESCRIPTION

LINKS

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, $\vec{X}$ and $\vec{Y}$ of $n$ components, $〈 X_{0}, \dots, X_{n - 1} 〉$ and $〈 Y_{0}, \dots, Y_{n - 1} 〉$ , $\vec{X}$ is lexicographically less than or equal to $\vec{Y}$ if and only if $n = 0$ or $X_{0} < Y_{0}$ or $X_{0} = Y_{0}$ and $〈 X_{1}, \dots, X_{n - 1} 〉$ is lexicographically less than or equal to $〈 Y_{1}, \dots, 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 〉$ ).

Typical

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | > 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.

Arg. properties

Suffix-contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ (remove items from same position).

Remark

The $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚_𝚊𝚕𝚕𝚙𝚎𝚛𝚖$ $(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2)$ can be reformulated as the conjunction $𝚜𝚘𝚛𝚝$ $(𝚅𝙴𝙲𝚃𝙾𝚁 2, 𝚅𝙴𝙲𝚃𝙾𝚁)$ , $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ $(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁)$ .

Systems

leximin in Choco.

Used in

$𝚊𝚕𝚕𝚙𝚎𝚛𝚖$ .

implies: $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ .

system of constraints: $𝚊𝚕𝚕𝚙𝚎𝚛𝚖$ .

Keywords

characteristic of a constraint: vector.

constraint type: predefined constraint, order constraint.

symmetry: symmetry, matrix symmetry, lexicographic order.

Global Constraint Catalog

5. Global Constraint Catalogue

5.233. lex_lesseq_allperm