15

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?

Michiel uit het Broek
  • 2,491
  • 2
  • 15
  • 36

5 Answers5

12

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.

Michael Trick
  • 2,362
  • 9
  • 34
  • 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 :) – Michiel uit het Broek Jun 03 '19 at 17:45
  • 1
    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? – Michael Trick Jun 03 '19 at 17:52
  • @Michiel Why don't you post a more OR-centric (and concise) answer than the one Michael Trick linked to? – LarrySnyder610 Jun 03 '19 at 21:03
  • 1
    @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 :) – Michiel uit het Broek Jun 04 '19 at 00:00
10

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.

Michiel uit het Broek
  • 2,491
  • 2
  • 15
  • 36
  • 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. – Michiel uit het Broek Jun 05 '19 at 10:36
  • 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. – Alexandre Frias Oct 02 '19 at 06:16
3

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.

Alexandre Frias
  • 676
  • 4
  • 7
3

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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
fpacaud
  • 1,501
  • 6
  • 7
1

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.

Josh Allen
  • 725
  • 3
  • 14