2

Suppose we have a binary variable $x$ and two non-negative continuous variables $y_1\ge 0$ and $y_2 \ge 0$. How can we linearize $xy_1 y_2$ ?

FYI, this is a follow up question to this: How to linearize the product of a binary and a non-negative continuous variable?

Youngwoo Sim
  • 31
  • 3
  • 2
    You cannot. Just consider the case when you don't have $x$, there is no magic way to linear a bilinear product of two continuous variables. – Johan Löfberg Aug 11 '22 at 10:48

2 Answers2

6

As Johan Löfberg said, it cannot be done directly. You can get an approximate solution in two steps.

  1. First, approximate the product of $y_1$ and $y_2$ using a new variable $z.$ See, for instance, this question, and specifically the answers involving McCormick envelopes.
  2. Now linearize the product of $x$ and $z$ using the link in your question.
prubin
  • 39,078
  • 3
  • 37
  • 104
6

I would start with a non-convex solver like Gurobi. Gurobi can only do quadratic terms, but that is not a real limitation:

 z1 = x*y1
 z2 = z1*y2
Erwin Kalvelagen
  • 2,676
  • 1
  • 6
  • 11