The CLP Procedure

LEXICO Statement

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 -tuples $x = (x_1, \dots , x_ n)$ and $y = (y_1, \dots , y_ n)$ , the -tuple is lexicographically less than or equal to ( $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 -tuple is lexicographically less than ( $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 -tuples in alphabetical order. Mathematically, $\le _{\mr {lex}}$ is a partial order on a given subset of -tuples, and $<_{\mr {lex}}$ is a strict partial order on a given subset of -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 for $i = 1,\dots ,4$ and . The fact that 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.