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$.