36

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

Michiel uit het Broek
  • 2,491
  • 2
  • 15
  • 36
  • 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: https://stackoverflow.blog/2011/07/01/its-ok-to-ask-and-answer-your-own-questions/ – Michiel uit het Broek May 31 '19 at 06:39
  • 5
    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. – Ehsan May 31 '19 at 07:25
  • Related: https://or.meta.stackexchange.com/questions/48/should-basic-questions-be-made-community-wikis – LarrySnyder610 May 31 '19 at 12:35

2 Answers2

38

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

Michiel uit het Broek
  • 2,491
  • 2
  • 15
  • 36
  • 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? – Hussein Sharadga Dec 27 '22 at 21:00
-1

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)

Hussein Sharadga
  • 409
  • 1
  • 10
  • 3
    These are the same four constraints as in the accepted answer. – RobPratt Dec 27 '22 at 21:27
  • Thanks@ RobPratt! I am not sure, but I guess the one found on page 7 of the Ref below is better: https://www.fico.com/en/resource-access/download/3217 (Section 2.8) – Hussein Sharadga Dec 27 '22 at 22:20
  • 3
    That one is a generalization. If you take $L=0$ (because $y$ in this question is nonnegative), you arrive at the same four constraints. – RobPratt Dec 27 '22 at 22:27