# How to linearize the product of two integer variables?

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

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.

• How about expressing only x (or only y) in terms of binary variables? Then you would have a smaller number of binary-times-general-integer products, and you could linearize them as described for example at orinanobworld.blogspot.com/2010/10/….
– 4er
Nov 16 '21 at 14:36
• Fair point! Feel free to post it as a separate answer. Otherwise, I'll edit my answer accordingly.
– joni
Nov 16 '21 at 14:41