Integer Variables and Quadratic Terms

This is a sequel to a previous post,"Binary Variables and Quadratic Terms", in which I described how to linearize the product of a binary variable and a general variable (possibly discrete, possibly continuous). Here I'll deal with linearizing $z=xy$ where $x\in X$, $X$ a discrete set, and $y$ is an arbitrary variable.

To linearize the product, I'll need both variables to bounded. So assume that $L\le y \le U$ and that $N_X=\left|X\right|\lt \infty$. There are a couple of ways (that I know) to proceed, and both involve introducing binary variables.

The more obvious route, suitable when $N_X$ is not large, is to add $N_X$ binary variables $w_a,\, a\in X$ and set\[x=\sum_{a\in X} aw_a,\]along with the SOS1 constraint\[\sum_{a\in X} w_a=1.\]Then\[z=\sum_{a\in X}aw_ay,\]and we can linearize each of the products $w_ay$ as explained in the previous post. More specifically, we set $z=\sum_{a\in X}az_a$ where $z_a=w_ay$ is a new continuous variable, then linearize the expression for $z_a$ (creating, per the previous post, four new constraints for each $z_a$).

The other approach is very similar but usually more efficient in terms of added variables and constraints when $X$ is an interval ($X=\{a, a + 1, \dots, a + N_X-1\}$) and $N_X$ is not small. Rather than creating a binary variable for each value in the domain $X$, we perform a binary expansion of $x$:\[x=a + \sum_{i=0}^{M} 2^iu_i\]with $u_0,\dots,u_{M}\in\{0,1\}$ and $M=\left\lfloor \log_{2}\left(N_{X}\right)\right\rfloor$. Unless $N_X$ happens to be an integral power of 2, we also need the constraint $x\le a+N_X-1$. The product $z=xy$ can now be written\[z=ay+\sum_{i=0}^M 2^iw_i\]where $w_i=u_iy$, and again we linearize each $w_i$ as explained in the prior post.