## 5.226. lex_chain_lesseq

Origin
Constraint

$\mathrm{𝚕𝚎𝚡}_\mathrm{𝚌𝚑𝚊𝚒𝚗}_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}\left(\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}\right)$

Usual name

$\mathrm{𝚕𝚎𝚡}_\mathrm{𝚌𝚑𝚊𝚒𝚗}$

Type
 $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Argument
 $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚎𝚌}-\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}\right)$
Restrictions
 $|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}|\ge 1$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂},\mathrm{𝚟𝚎𝚌}\right)$ $\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚜𝚒𝚣𝚎}$$\left(\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂},\mathrm{𝚟𝚎𝚌}\right)$
Purpose

For each pair of consecutive vectors ${\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}}_{i}$ and ${\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}}_{i+1}$ of the $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ collection we have that ${\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}}_{i}$ is lexicographically less than or equal to ${\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}}_{i+1}$. Given two vectors, $\stackrel{\to }{X}$ and $\stackrel{\to }{Y}$ of $n$ components, $〈{X}_{0},\cdots ,{X}_{n-1}〉$ and $〈{Y}_{0},\cdots ,{Y}_{n-1}〉$, $\stackrel{\to }{X}$ is lexicographically less than or equal to $\stackrel{\to }{Y}$ if and only if $n=0$ or ${X}_{0}<{Y}_{0}$ or ${X}_{0}={Y}_{0}$ and $〈{X}_{1},\cdots ,{X}_{n-1}〉$ is lexicographically less than or equal to $〈{Y}_{1},\cdots ,{Y}_{n-1}〉$.

Example
$\left(〈\mathrm{𝚟𝚎𝚌}-〈5,2,3,9〉,\mathrm{𝚟𝚎𝚌}-〈5,2,6,2〉,\mathrm{𝚟𝚎𝚌}-〈5,2,6,2〉〉\right)$

The $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚌𝚑𝚊𝚒𝚗}_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}$ constraint holds since:

• The first vector $〈5,2,3,9〉$ of the $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ collection is lexicographically less than or equal to the second vector $〈5,2,6,2〉$ of the $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ collection.

• The second vector $〈5,2,6,2〉$ of the $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ collection is lexicographically less than or equal to the third vector $〈5,2,6,2〉$ of the $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ collection.

Typical
 $|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁}|>1$ $|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}|>1$
Arg. properties
• Contractible wrt. $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$.

• Suffix-contractible wrt. $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}.\mathrm{𝚟𝚎𝚌}$ (remove items from same position).

Usage

This constraint was motivated for breaking symmetry: more precisely when one wants to lexicographically order the consecutive columns of a matrix of decision variables. A further motivation is that using a set of lexicographic ordering constraints between two vectors does usually not allows to come up with a complete pruning.

Algorithm

A filtering algorithm achieving arc-consistency for a chain of lexicographical ordering constraints is presented in [BeldiceanuCarlsson02c].

Six different ways of integrating a chain of lexicographical ordering constraints within non-overlapping constraints like $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ or $\mathrm{𝚐𝚎𝚘𝚜𝚝}$ and within their corresponding necessary condition like the $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraint are shown in [AgrenCarlssonBeldiceanuSbihiTruchetZampelli09].

Systems

common keyword: $\mathrm{𝚊𝚕𝚕𝚙𝚎𝚛𝚖}$ (lexicographic order), $\mathrm{𝚐𝚎𝚘𝚜𝚝}$ (symmetry, lexicographic ordering on the origins of $\mathrm{𝚝𝚊𝚜𝚔𝚜}$, $\mathrm{𝚛𝚎𝚌𝚝𝚊𝚗𝚐𝚕𝚎𝚜}$, $...$), $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚋𝚎𝚝𝚠𝚎𝚎𝚗}$, $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚐𝚛𝚎𝚊𝚝𝚎𝚛}$, $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚}$, $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚕𝚎𝚜𝚜}$ (lexicographic order).

implied by: $\mathrm{𝚕𝚎𝚡}\mathtt{2}$ (columns lex ordering imposed by constraint $\mathrm{𝚕𝚎𝚡}\mathtt{2}$ removed), $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚌𝚑𝚊𝚒𝚗}_\mathrm{𝚕𝚎𝚜𝚜}$ (non-strict order implied by strict order),

$\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}_\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$ ($\mathrm{𝙽𝚅𝙴𝙲}$ of constraint $\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}_\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$ removed),

$\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$ ($\mathrm{𝙽𝚅𝙴𝙲}$ of constraint $\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$ removed),

$\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$ ($\mathrm{𝙽𝚅𝙴𝙲}$ of constraint $\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$ removed).

related: $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$, $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ (lexicographic ordering on the origins of $\mathrm{𝚝𝚊𝚜𝚔𝚜}$, $\mathrm{𝚛𝚎𝚌𝚝𝚊𝚗𝚐𝚕𝚎𝚜}$, $...$).

Keywords
Arc input(s)

$\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$

Arc generator
$\mathrm{𝑃𝐴𝑇𝐻}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚎𝚌𝚝𝚘𝚛𝚜}\mathtt{1},\mathrm{𝚟𝚎𝚌𝚝𝚘𝚛𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚕𝚎𝚡}_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}$$\left(\mathrm{𝚟𝚎𝚌𝚝𝚘𝚛𝚜}\mathtt{1}.\mathrm{𝚟𝚎𝚌},\mathrm{𝚟𝚎𝚌𝚝𝚘𝚛𝚜}\mathtt{2}.\mathrm{𝚟𝚎𝚌}\right)$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}|-1$

Graph model

Parts (A) and (B) of Figure 5.226.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐍𝐀𝐑𝐂}$ graph property, the arcs of the final graph are stressed in bold. The $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚌𝚑𝚊𝚒𝚗}_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}$ constraint holds since all the arc constraints of the initial graph are satisfied.

##### Figure 5.226.1. Initial and final graph of the $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚌𝚑𝚊𝚒𝚗}_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}$ constraint  (a) (b)
Signature

Since we use the $\mathrm{𝑃𝐴𝑇𝐻}$ arc generator on the $\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}$ collection the number of arcs of the initial graph is equal to $|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}|-1$. For this reason we can rewrite $\mathrm{𝐍𝐀𝐑𝐂}=|\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}|-1$ to $\mathrm{𝐍𝐀𝐑𝐂}\ge |\mathrm{𝚅𝙴𝙲𝚃𝙾𝚁𝚂}|-1$ and simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.