Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
$\begingroup$
$\endgroup$
3
asked May 31, 2019 at 6:37
-
$\begingroup$ To generate more expected content for our new OR forum and since it is allowed to answers your own questions: I added this basic OR questions. see: stackoverflow.blog/2011/07/01/… $\endgroup$– Michiel uit het BroekMay 31, 2019 at 6:39
-
5$\begingroup$ I think it's a good idea to have a question dedicated to this type of questions (how to linearize X * Y where ...). On OR-X, we have lots of questions dedicated to the linearization of products or division. This question could be a reference point for future similar questions. If you agree, we could make this a Wiki question and the community develop it over time. $\endgroup$– EhsanMay 31, 2019 at 7:25
-
$\begingroup$ Related: or.meta.stackexchange.com/questions/48/… $\endgroup$– LarrySnyder610May 31, 2019 at 12:35
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Suppose we can give a finite upper bound for $y$ called $M$. Then this constraint can easily be linearized by using the so-called big $M$ method. We introduce a new variable $z$ that should take the same value as the product $x y$.
Notice that the product which we model by $z$ equals zero if $x = 0$ but $z$ can take any value between $0$ and $M$ if $x = 1$. We can model this by using $z \leq x M$. Next, the product is always non-negative and smaller than $y$, thus $z\geq 0$ and $z \leq y$.
It is left to force $z$ to equal $y$ in case $x = 1$ which we obtain with $$ z \geq y - (1 - x)M. $$
answered May 31, 2019 at 6:37
-
$\begingroup$ If M is 10. At x=0: z>=y-M. y can be any number between 0 and 10. If y =1: z>1-10, then z>-9; z is not necessarily equal to zero contrary to what you stated. Can you please explain more? $\endgroup$ Dec 27, 2022 at 21:00
$\begingroup$
$\endgroup$
3
The four required constraints are summarized below for non-negative case:
$z<=M.x$ (1)
$z<=y$ (2)
$z>=y-(1-x).M$ (3)
$z>=0$ (4)
For negative and nonnegative, the general formula is give here: https://www.fico.com/en/resource-access/download/3217 (page 7, section 2.8)
-
2$\begingroup$ These are the same four constraints as in the accepted answer. $\endgroup$– RobPrattDec 27, 2022 at 21:27
-
$\begingroup$ Thanks@ RobPratt! I am not sure, but I guess the one found on page 7 of the Ref below is better: fico.com/en/resource-access/download/3217 (Section 2.8) $\endgroup$ Dec 27, 2022 at 22:20
-
2$\begingroup$ That one is a generalization. If you take $L=0$ (because $y$ in this question is nonnegative), you arrive at the same four constraints. $\endgroup$– RobPrattDec 27, 2022 at 22:27