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.