The CLP Procedure

LEXICO Statement

(Experimental)

LEXICO lexicographic_ordering_constraint-1 <…lexicographic_ordering_constraint-n> ;

LEXORDER lexicographic_ordering_constraint-1 <…lexicographic_ordering_constraint-n> ;

where lexicographic_ordering_constraint is specified in the following form:

((variable-list-1) order_type (variable-list-2))

where variable-list-1 and variable-list-2 are variable lists of equal length. The keyword order_type signifies the type of ordering and can be one of two values: LEX_LE, which indicates lexicographically less than or equal to ($\le _{\mr {lex}}$), or LEX_LT, which indicates lexicographically less than ($<_{\mr {lex}}$).

The LEXICO statement specifies one or more lexicographic constraints. The lexicographic constraint $\le _{\mr {lex}}$ and the strict lexicographic constraint $<_{\mr {lex}}$ are defined as follows. 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 given subset of $n$-tuples, and $<_{\mr {lex}}$ is a strict partial order on a given 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 statement as follows:

lexico( (x1-x6) lex_le (y1-y6) );

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 kind of symmetry that arises in CSPs with matrices of decision variables. Frisch et al. (2002) introduce an optimal algorithm to establish GAC (generalized arc consistency) for the $\le _{\mr {lex}}$ constraint between two vectors of variables.