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

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

2 Answers 2


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

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

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$
    – RobPratt
    Dec 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$
    – RobPratt
    Dec 27, 2022 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.