14
$\begingroup$

Suppose we have two variables $x, y \in \mathbb R$. How can we linearize the product $xy$?

If this cannot be done exactly, is there a way to get an approximate result?

$\endgroup$
0

5 Answers 5

12
$\begingroup$

Unlike cases where one or both of the $x$ and $y$ are binary, you won't be able to truly (i.e. exactly) linearize this. https://stackoverflow.com/questions/49021401/how-to-linearize-the-product-of-two-float-variables goes through the approximation approach to this issue.

$\endgroup$
4
  • $\begingroup$ That's true! I hope someone will introduce the method with the new variables $y_1 = 0.5(x - y)$ and $y_2 = 0.5(x + y)$ here on our forum and then explains how this can be used to approximate the original problem. Indeed this question is meant to fill the new forum during its beta stage :) $\endgroup$ Jun 3, 2019 at 17:45
  • 1
    $\begingroup$ My bad! Perhaps a more useful answer would have been one aimed at an OR audience (though the one I point to is reasonably accessible to the OR world). Any takers? $\endgroup$ Jun 3, 2019 at 17:52
  • $\begingroup$ @Michiel Why don't you post a more OR-centric (and concise) answer than the one Michael Trick linked to? $\endgroup$ Jun 3, 2019 at 21:03
  • 1
    $\begingroup$ @LarrySnyder610 for two reasons: 1) I try to create opportunities for other users to reach 200 reputation points as we need this to pass the beta stage, and 2) I am at the MMR conference and do not have too much time left. If the answer is not given within a week or so, then I'll write it myself :) $\endgroup$ Jun 4, 2019 at 0:00
9
$\begingroup$

As far as I know, there is no true way to linearize such constraints, as also stated in the answer given by Michael Trick. Let us therefore consider a piecewise linear approximation of the constraint $x_1 x_2 \geq b$ where $x_1, x_2 \in \mathbb R$ and $b$ is a given constant.

The method discussed in this answer is introduced in the AIMMS Modelling Guide in section 7.7 on page 85.

The method introduces two new variables $$ \begin{align} y_1 &= 0.5(x_1 + x_2),\\ y_2 &= 0.5(x_1 - x_2). \end{align} $$ Now we can rewrite the constraint $x_1x_2 \geq b$ as $$y_1^2 - y_2^2 \geq b.$$ This is indeed again not a linear constraint, but this constraint can be approximated with piecewise linear approximation techniques (see section 7.6 of the AIMMS Modelling Guide) as the left-hand-side is now a separable function.

$\endgroup$
2
  • $\begingroup$ The special case where both variables are non-negative and one is only present in this constraint can be dealt with without approximation. I will add that special case later as I have no time now. $\endgroup$ Jun 5, 2019 at 10:36
  • $\begingroup$ Let $M>b$ be a big number. For $x_1>M$ and $x_2>M$ you can use the asymptotic line of the hyperbola $y_1 - y_2 =0$. Probably, the error is almost zero. $\endgroup$ Oct 2, 2019 at 6:16
3
$\begingroup$

In addition, you can search for McCormick Envelopes in this site:

McCormick

For example, $0\leq x \leq 1$ and $0\leq y\leq 1$. By substituition $z=xy$ then $0\leq z\leq 1$

$$ \begin{align} z\leq x\\ z\leq y\\ z\geq x+y-1 \end{align} $$

but, it is a relaxation for continuous variables. Note that $x=0.5$ and $y=0.5$ then $0\leq z\leq 0.5$ and not $z=0.25$. For binary variables this method is exact.

$\endgroup$
3
$\begingroup$

A good reference for McCormick envelopes can be found here.

Note that the quality of the relaxation is quite impacted by the bounds $x_L, x_U$ and $y_L, y_U$ we have on the two variables $x$ and $y$: the tighter, the better.

$\endgroup$
2
  • $\begingroup$ Don't you mean, the tighter, the better? $\endgroup$ Oct 10, 2019 at 20:50
  • 1
    $\begingroup$ Indeed! I edited the post accordingly. $\endgroup$
    – fpacaud
    Oct 11, 2019 at 6:28
1
$\begingroup$

To complement the other answers, one can also approach this using piecewise McCormick relaxations. References and examples for how this works can be found here and here.

$\endgroup$

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.