The Constraint Programming Solver

LEXICO Predicate

  • LEXICO (variable-list order-type variable-list)

The LEXICO predicate defines a lexicographic ordering constraint, which compares two arrays of the same size from left to right. For example, a standings table in a sports competition is usually ordered lexicographically, with certain attributes (such as wins or points) to the left of others (such as goal difference).

The order-type can be either $\le $, to indicate lexicographically less than or equal to ($\le _{\mr{lex}}$), or $<$, to indicate lexicographically less than ($<_{\mr{lex}}$). Given two n-tuples $x = (x_1, \dots , x_ n)$ and $y = (y_1, \dots , y_ n)$, the n-tuple x is lexicographically less than or equal to y ($x \le _{\mr{lex}} y$) if and only if

\[ \bigl (x_ i = y_ i \: \forall i = 1, \dots , n\bigr ) \vee \left(\exists j \mbox{ with } 1 \leq j \leq n \mbox{ s.t. } x_ i = y_ i \: \forall i = 1, \dots , j\! -\! 1 \mbox{ and } x_ j < y_ j\right) \]

The n-tuple x is lexicographically less than y ($x <_{\mr{lex}} y$) if and only if $x \le _{\mr{lex}} y$ and $x \neq y$. Equivalently, $x <_{\mr{lex}} y$ if and only if

\[ \exists j \mbox{ with } 1 \leq j \leq n \mbox{ s.t. } x_ i = y_ i \: \forall i = 1, \dots , j\! -\! 1 \mbox{ and } x_ j < y_ j \]

Informally, you can think of the lexicographic constraint $\le _{\mr{lex}}$ as sorting the n-tuples in alphabetical order. Mathematically, $\le _{\mr{lex}}$ is a partial order on a subset of n-tuples, and $<_{\mr{lex}}$ is a strict partial order on a subset of n-tuples (Brualdi 2010).

For example, you can express the lexicographic constraint ${(X[1],\dots , X[6]) \le _{\mr{lex}} (Y[1],\dots , Y[6])}$ by using a LEXICO predicate as follows:

con Mycon: lexico({j in 1..6} X[j] <= {j in 1..6} Y[j]);

The assignment ${X[1]\! =\! 1}$, ${X[2]\! =\! 2}$, ${X[3]\! =\! 2}$, ${X[4]\! =\! 1}$, ${X[5]\! =\! 2}$, ${X[6]\! =\! 5}$, ${Y[1]\! =\! 1}$, ${Y[2]\! =\! 2}$, ${Y[3]\! =\! 2}$, ${Y[4]\! =\! 1}$, ${Y[5]\! =\! 4}$, and ${Y[6]\! =\! 3}$ satisfies this constraint because $X[i] = Y[i]$ for $i = 1,\dots ,4$ and $X[5] < Y[5]$. The fact that $X[6] > Y[6]$ is irrelevant in this ordering.

Lexicographic ordering constraints can be useful for breaking a certain type of symmetry that arises in CSPs and involves matrices of decision variables. Frisch et al. (2002) introduce an optimal algorithm to establish generalized arc consistency (GAC) for the $\le _{\mr{lex}}$ constraint between two vectors of variables.