Element Constraints for Variable Indexing

In constraint programming, we often need to express the value at position $i$ of a list, where the index $i$ is itself a decision variable. Standard indexing $v[i]$ requires $i$ to be a known integer at modeling time, but a solver only fixes $i$ at solve time.

The element constraint resolves this. Given an integer-valued list $v=[v_0, v_1, \ldots, v_{n-1}]$, an index variable $i$, and a target variable $y$, the call

$$\texttt{AddElement}(i,\; [v_0, v_1, \ldots, v_{n-1}],\; y)$$

enforces the relationship

$$y = v_i.$$

The index $i$ is restricted to $\{0, 1, \ldots, n-1\}$. Whenever the solver fixes $i$ to a particular value, $y$ is forced to equal the entry of $v$ at that position.

For example, the constraint

$$\texttt{AddElement}(i,\; [3, 8, 1, 6, 4],\; y)$$

forces $y=3$ when $i=0$, $y=1$ when $i=2$, and $y=4$ when $i=4$.

The same logical effect could be obtained with reified constraints, one per possible index value ($y=3$ $\texttt{OnlyEnforceIf}$ ($i=0$), $y=8$ $\texttt{OnlyEnforceIf}$ ($i=1$), and so on). The element constraint is the compact, solver-friendly way to express the same idea.