The Constraint Programming Solver (Experimental)

LEXICO Predicate

LEXICO (variable-list relational-operator 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).

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.