How to linearize the product of two integer variables?

Question

Given two integer variables $L_x \leq x \leq U_x$ and $L_y \leq y \leq U_y$, how can we linearize the product $x \cdot y$?

Answer 1

A straightforward approach is to express the integer variables $x$ and $y$ in terms of binary variables. In case $L_x < 0$ or $L_y < 0$, we can use the two complement's representation, see this answer for more details. So let's assume $L_x, L_y \geq 0$. Then, we have

$$ x \cdot y = \left( \sum_{i=0}^{M_x - 1} 2^i x_i \right) \cdot \left( \sum_{j=0}^{M_y - 1} 2^j y_j \right) = \sum_{i=0}^{M_x -1} \sum_{j=0}^{M_y-1} 2^{i+j} x_i y_j, $$

with $M_x = \left\lceil \log_2{(U_x + 1)} \right\rceil$ binary variables $x_i$ and $M_y = \left\lceil \log_2{(U_y + 1)} \right\rceil$ binary variables $y_j$. Now we can linearize the products of two binary variables $z_{ij} = x_iy_j$ by introducing additional binary variables $z_{ij}$ and imposing the constraints

$$ \begin{align} z_{ij} &\leq x_i, \\ z_{ij} &\leq y_j, \\ z_{ij} &\geq x_i + y_j - 1, \end{align} $$

for all $i = 0, \ldots, M_x-1, j = 0, \ldots, M_y - 1$. Since $M_xM_y + M_x + M_y$ binary variables are required to linearize the integer product $x \cdot y$, this approach is only worth if $x$'s and $y$'s range of values is small.

---

Edit: As 4er mentioned in the comments, we can significantly reduce the number of required binary variables by only expressing $x$ in terms of binary variables. Let again assume $L_x \geq 0$. Then,

$$ x \cdot y = \left( \sum_{i=0}^{M_x - 1} 2^i x_i \right) \cdot y = \sum_{i=0}^{M_x - 1} 2^i x_i y. $$

Consequently, we only need to linearize the $M_x$ products $z_i = x_i y$ of a binary and an integer variable by imposing the constraints

$$ \begin{align} z_i &\leq U_y x_i \\ z_i &\geq L_y x_i \\ z_i &\leq y - L_y (1-x_i) \\ z_i &\geq y - U_y (1-x_i) \\ \end{align} $$

for all $i = 0, \ldots, M_x - 1$. Thus, only $M_x$ binary variables and $M_x$ general variables need to be introduced.