DOCUMENTATION
Sign In

Get access to My SAS, trials, communities and more.

Mathematical Optimization Procedures
 

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 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 (less-than-or-equal-to Subscript normal l normal e normal x Baseline), or LEX_LT, which indicates lexicographically less than (less-than Subscript normal l normal e normal x Baseline).

The LEXICO statement specifies one or more lexicographic constraints. The lexicographic constraint less-than-or-equal-to Subscript normal l normal e normal x Baseline and the strict lexicographic constraint less-than Subscript normal l normal e normal x Baseline are defined as follows. Given two n-tuples x equals left-parenthesis x 1 comma ellipsis comma x Subscript n Baseline right-parenthesis and y equals left-parenthesis y 1 comma ellipsis comma y Subscript n Baseline right-parenthesis, the n-tuple x is lexicographically less than or equal to y (x less-than-or-equal-to Subscript normal l normal e normal x Baseline y) if and only if

The n-tuple x is lexicographically less than y (x less-than Subscript normal l normal e normal x Baseline y) if and only if x less-than-or-equal-to Subscript normal l normal e normal x Baseline y and x not-equals y. Equivalently, x less-than Subscript normal l normal e normal x Baseline y if and only if

Frisch et al. (2002) introduced an optimal algorithm to establish generalized arc consistency (GAC) for the less-than-or-equal-to Subscript normal l normal e normal x Baseline constraint between two vectors of variables. Informally you can think of the lexicographic constraint less-than-or-equal-to Subscript normal l normal e normal x Baseline as sorting the n-tuples in alphabetical order. Mathematically, less-than-or-equal-to Subscript normal l normal e normal x Baseline is a partial order on a given subset of n-tuples, and less-than Subscript normal l normal e normal x Baseline is a strict partial order on a given subset of n-tuples (Brualdi 2010).

For example, you can express the lexicographic constraint left-parenthesis x 1 comma ellipsis comma x 6 right-parenthesis less-than-or-equal-to Subscript normal l normal e normal x Baseline left-parenthesis y 1 comma ellipsis comma y 6 right-parenthesis by using a LEXICO statement as follows: 

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

The assignment x 1 equals 1, x 2 equals 2, x 3 equals 2, x 4 equals 1, x 5 equals 2, x 6 equals 5, y 1 equals 1, y 2 equals 2, y 3 equals 2, y 4 equals 1, y 5 equals 4, and y 6 equals 3 satisfies this constraint because x Subscript i Baseline equals y Subscript i for i equals 1 comma ellipsis comma 4 and x 5 less-than y 5. The fact that x 6 greater-than 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.

Copyright © SAS Institute Inc. All rights reserved.
Last updated: May 08, 2020