36
$\begingroup$

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

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

2 Answers 2

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

$\endgroup$
1
  • $\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$ Commented Dec 27, 2022 at 21:00
-1
$\begingroup$

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)

$\endgroup$
3
  • 3
    $\begingroup$ These are the same four constraints as in the accepted answer. $\endgroup$
    – RobPratt
    Commented 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$ Commented Dec 27, 2022 at 22:20
  • 3
    $\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
    Commented Dec 27, 2022 at 22:27

Your Answer

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

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