15
$\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$
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.

| improve this answer | |
$\endgroup$
  • $\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$ – Michiel uit het Broek Jun 3 '19 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$ – Michael Trick Jun 3 '19 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$ – LarrySnyder610 Jun 3 '19 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$ – Michiel uit het Broek Jun 4 '19 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.

| improve this answer | |
$\endgroup$
  • $\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$ – Michiel uit het Broek Jun 5 '19 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$ – Alexandre Frias Oct 2 '19 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.

| improve this answer | |
$\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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Don't you mean, the tighter, the better? $\endgroup$ – Robert Schwarz Oct 10 '19 at 20:50
  • 1
    $\begingroup$ Indeed! I edited the post accordingly. $\endgroup$ – fpacaud Oct 11 '19 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.

| improve this answer | |
$\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.