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?
$\begingroup$
$\endgroup$
0
asked Jun 3, 2019 at 14:54
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
4
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.
-
$\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
$\begingroup$
$\endgroup$
2
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.
answered Jun 3, 2019 at 15:01
-
$\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
$\begingroup$
$\endgroup$
In addition, you can search for McCormick Envelopes in this site:
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.
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Don't you mean, the tighter, the better? $\endgroup$ Oct 10, 2019 at 20:50
-
1
