2
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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/…. $\endgroup$
    – 4er
    Nov 16 '21 at 14:36
  • $\begingroup$ Fair point! Feel free to post it as a separate answer. Otherwise, I'll edit my answer accordingly. $\endgroup$
    – joni
    Nov 16 '21 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.