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 '19 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 '19 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 '19 at 7:25
-
$\begingroup$ Related: or.meta.stackexchange.com/questions/48/… $\endgroup$– LarrySnyder610 ♦May 31 '19 at 12:35
Add a comment
|
$\begingroup$
$\endgroup$
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 '19 at 6:37