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 binding valueBinding and may involve variables.

secondValues
The expression that should lexicographically come after firstValues. It is defined over index binding valueBinding and may involve variables.

allowEqual
When this optional argument is specified and non-zero, the expressions firstValues and secondValues are allowed to be equal. The allowEqual 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 identifier x comes lexicographically before the identifier y.

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 and y = 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, the x- and y-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     1

Here AIMMS visits all elements of the two dimensional variables x and y, by varying the indices i and j in the index binding (i,j) and adhering to the index domain condition ord(i)<=ord(j). In the index binding (i,j) the index j comes after the index i and thus the index j is varied more.

cp::Lexicographic

Mathematical Formulation

Function Prototype

Arguments

Return Value

Example

Docs

Product

Support