# How to linearize the product of a binary and a non-negative continuous variable?

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

• 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/… May 31, 2019 at 6:39
• 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. May 31, 2019 at 7:25
• May 31, 2019 at 12:35

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

• 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? 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)

• These are the same four constraints as in the accepted answer. Dec 27, 2022 at 21:27
• 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) Dec 27, 2022 at 22:20
• That one is a generalization. If you take $L=0$ (because $y$ in this question is nonnegative), you arrive at the same four constraints. Dec 27, 2022 at 22:27