Saturday, July 6, 2013

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.

No comments:

Post a Comment

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.