23
$\begingroup$

Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?

$\endgroup$
  • $\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 Broek May 31 at 6:39
  • 4
    $\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$ – Ehsan May 31 at 7:25
  • $\begingroup$ Related: or.meta.stackexchange.com/questions/48/… $\endgroup$ – LarrySnyder610 May 31 at 12:35
23
$\begingroup$

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 enforce 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. $$

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