## 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://orinanobworld.blogspot.com/2013/07/integer-variables-and-quadratic-terms.html", "fetch_time": 1490806976000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2017-13/segments/1490218190754.6/warc/CC-MAIN-20170322212950-00093-ip-10-233-31-227.ec2.internal.warc.gz", "warc_record_offset": 257183183, "warc_record_length": 25748, "token_count": 551, "char_count": 1801, "score": 4.03125, "int_score": 4, "crawl": "CC-MAIN-2017-13", "snapshot_type": "longest", "language": "en", "language_score": 0.8585302829742432, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00061-of-00064.parquet"}