Indexing an Array with a Variable

Sometimes, in the context of a mathematical program, someone wants to use a variable $x$ to index a vector $y$, as in $$z = y[x].$$ As a starting point, we should assume that $x$ is an integer variable whose domain equals, or at least is a subset of, the index set of $y$. If you try to set $z=y[2.71828]$, or $z=y[5]$ when $y$ is indexed by ${1,\dots,4}$, you should expect Bad Things To Happen.

With that stipulation, $z=y[x]$ poses no problem in a constraint program. It cannot, however, be expressed directly in a mathematical program. If the domain of $x$ is not too large, it can be implemented somewhat obliquely in a mathematical program using binary variables.

Let's assume that $y$ is indexed over $1,\dots,N$ (with $N$ known at the outset), and that $y$ is a parameter. (We'll treat the case where $y$ is a variable in a minute.) Create $N$ binary variables $x_1,\dots,x_N$ and add the constraint $$x_1+\dots+x_N=1,$$ which makes $\{x_1,\dots,x_N\}$ a type 1 special ordered set (SOS1). Then define $z$ via $$z=\sum_{i=1}^N y[i]*x_i.$$

You can do exactly this when $y$ is a vector of variables, but it adds a nonconvex quadratic constraint to the model, which likely prevents you from finding a guaranteed optimum, and greatly restricts what algorithms/software you can use. If we know a priori lower and upper bounds for $y$, say $$L_i \le y[i] \le U_i \forall i\in {1,\dots,N}$$ with $L_i$ and $U_i$ parameters, we can add the $x_i$ as above and use the following set of constraints to define $z$: $$\begin{eqnarray*}y[i] -z \le (U_i - \hat{L})(1-x_i)  \forall i\in {1,\dots,N}\\ y[i] - z \ge (L_i - \hat{U})(1-x_i)  \forall i\in {1,\dots,N}\end{eqnarray*}$$ where $\hat{L}=\min_{i=1,\dots,N} L_i$ and $\hat{U}=\max_{i=1,\dots,N} U_i$.