- Function cp::Lexicographic(valueBinding, firstValues, secondValues, allowEqual)
cp::Lexicographic
The function cp::Lexicographic
ensures that the data of one
expression comes lexicographically (i.e. according to the set order)
before another expression. This function is often used to reduce
symmetry in two variables.
Mathematical Formulation
cp::Lexicographic(k,x_k,y_k[,e])
is equivalent to\[\begin{split}\exists i \in \{1..n\} : (\forall j: j < i: x_j=y_j)\wedge \left\{ \begin{array}{ll} x_i<y_i & \textrm{if } e = 0 \\ x_i\leq y_i & \textrm{if } e \neq 0 \\ \end{array} \right.\end{split}\]where \(n\) equals
card(range(k))
.
Function Prototype
cp::Lexicographic( valueBinding, ! (input) an index binding firstValues, ! (input/output) an expression secondValues, ! (input/output) an expression allowEqual ! (optional input) an expression )
Arguments
- valueBinding
The index binding over which the next two arguments are defined.
- firstValues
The expression that should lexicographically come before
secondValues
. It is defined over index bindingvalueBinding
and may involve variables.- secondValues
The expression that should lexicographically come after
firstValues
. It is defined over index bindingvalueBinding
and may involve variables.- allowEqual
When this optional argument is specified and non-zero, the expressions
firstValues
andsecondValues
are allowed to be equal. TheallowEqual
expression may not involve variables. The default of this argument is 0.
Return Value
This function returns 1 if the above condition is met. When the index binding
valueBinding
is empty, this function returns
0 if allowEqual is 0
1 if allowEqual is not 1.
Note
Please note that the comparison between the two expressions is done, based on the complete specified index binding and not pair-wise for every element in that index domain.
Example
The constraint
x_before_y
ensures that the identifierx
comes lexicographically before the identifiery
.Constraint x_before_y { Definition : cp::Lexicographic( i, x(i), y(i) ); }Suppose
x = data { 'a1' : 1, 'a2' : 2, 'a3' : 2 } y = data { 'a1' : 1, 'a2' : 3, 'a3' : 1 }Then the constraint
x_before_y
is met. Please note that in the case of ‘a3’,x = 2
andy = 1
. Allthough 2 does not come lexicographically before 1, the constraint is met. The ordering is based on the whole index domain, and not ‘pair wise’. Because for ‘a2’ 2 comes lexicographically before 3, thex
- andy
-values for ‘a3’ are irrelevant here. Higher dimensional variables can also be compared using cp::Lexicographic as is illustrated next. Consider the following declarations:Set S { Index : i, j; InitialData : data { a, b, c }; } Variable X { IndexDomain : (i,j); Range : binary; } Variable Y { IndexDomain : (i,j); Range : binary; } Constraint xylex { Definition : { cp::Lexicographic( (i,j)|ord(i)<=ord(j), x(i,j), y(i,j)) } }Instantiated constraints are presented in the constraint listing. For the constraint
xylex
this looks as follows:---- xylex xylex .. [ 1 | 1 | after ] cp::Lexicographic({X(a,a), X(a,b), X(a,c), X(b,b), X(b,c), X(c,c)}, {Y(a,a), Y(a,b), Y(a,c), Y(b,b), Y(b,c), Y(c,c)}, allowEqual: 0) name lower level upper X(a,a) 0 0 1 X(a,b) 0 0 1 X(a,c) 0 0 1 X(b,b) 0 0 1 X(b,c) 0 0 1 X(c,c) 0 0 1 Y(a,a) 0 1 1 Y(a,b) 0 0 1 Y(a,c) 0 0 1 Y(b,b) 0 0 1 Y(b,c) 0 0 1 Y(c,c) 0 0 1Here AIMMS visits all elements of the two dimensional variables
x
andy
, by varying the indicesi
andj
in the index binding(i,j)
and adhering to the index domain conditionord(i)<=ord(j)
. In the index binding(i,j)
the indexj
comes after the indexi
and thus the indexj
is varied more.
See also
The help text associated with the option
constraint_listing
. This option can be found via the AIMMS menusettings
>project options
categorySolvers general
>Standard reports
>constraints
.Constraint Programming on Constraint Programming in the Language Reference.
The Global Constraint Catalog, which references this function as
lex_less
andlex_lesseq
.