The Constraint Programming Solver (Experimental)

ELEMENT Predicate

  • ELEMENT (scalar-variable,data-list,variable)

The ELEMENT predicate specifies an array element lookup constraint, which enables you to define dependencies (which are not necessarily functional) between variables.

The predicate ELEMENT$(I, L, V)$ sets the variable V to be equal to the Ith element in the list L, where $L = (v_1,\ldots ,v_ n)$ is a list of values (not necessarily distinct) that the variable V can take. The variable I is the index variable, and its domain is considered to be $[1, n]$. Each time the domain of I is modified, the domain of V is updated, and vice versa.

For example, the following statements use the ELEMENT predicate to determine whether there are squares greater than 1 that are also elements of the Fibonacci sequence:

/* Are there any squares > 1 in the Fibonacci sequence? */
proc optmodel;
   num n = 20;
   /* 1 appears twice in the Fibonacci sequence */
   num fib{i in 1..n} = if i < 3 then 1 else fib[i-1] + fib[i-2];

   var IFib integer, ISq integer,
       XFib integer, XSq integer;

   con IsFibAndIsSquare: XFib = XSq;
   /* You can use a numeric array to refer to a list */
   con IdxOfFib: element( IFib, fib, XFib );
   /* You can also build a list from a set iterator */
   con IdxOfSq:  element( ISq,  {i in 2..n} (i * i),  XSq );
   solve;
   print XFib XSq;
quit;

An element constraint enforces the propagation rules

\[  V=v \Leftrightarrow I \in \{ i_1,\ldots ,i_ m\}   \]

where v is a value in the list L and $i_1,\ldots ,i_ m$ are all the indices in L whose value is v.

An element constraint is equivalent to a conjunction of reify and linear constraints. For example, both of the following examples implement the quadratic function, $Y=X^2$:

  • Using the ELEMENT predicate:

    proc optmodel;
       var X >= 1 <= 5 integer, Y >= 1 <= 25 integer;
       num a {i in 1..5} = i^2;
       con Mycon: element(X, a, Y);
       solve;
    quit;
    
    
  • Using linear constraints and the REIFY predicate:

    proc optmodel;
       var X >= 1 <= 5 integer, Y >= 1 <= 25 integer, R {1..5} binary;
       con MyconX {i in 1..5}:
          reify(R[i], X = i);
       con MyconY {i in 1..5}:
          reify(R[i], Y = i^2);
       con SumToOne:
          sum {i in 1..5} R[i] = 1;
       solve;
    quit;
    
    

You can also use element constraints to define positional mappings between two variables. For example, suppose the function $Y=X^2$ is defined on only odd numbers in the interval $[-5, 5]$. You can relate X and Y by using two element constraints and an artificial index variable:

var I integer, X integer, Y integer;
/* You can also build a list by providing explicit literals. */
con XsubI: element (I, -5 -3 -1 1 3  5, X);
con YsubI: element (I, 25  9  1 1 9 25, Y);