1
$\begingroup$

Suppose we have a binary variable $b \in \{0, 1\}$ and a continuous (possibly negative) variable $y \in \mathbb{R}$. How can we linearize the product $b \cdot y$?

$\endgroup$
1
  • $\begingroup$ Similar to the case of non-negative $y$, I added this basic OR question since it is allowed to answer your own questions and AFAIK this question was still missing. $\endgroup$
    – joni
    Apr 11 at 7:24
4
$\begingroup$

Suppose we know an upper bound $M$ for $y$ such that $|y| \leq M$, we can linearize this constraint as follows. First, we introduce a new variable $h \in \mathbb{R}$ with $h = b y$. Then we need to model that $h$ equals $y$ if $b = 1$ and equals $0$ if $b = 0$. For this purpose we add the following linear constraints:

$$ \begin{align} h &\leq b M \tag{1} \\ h &\geq -b M \tag{2} \\ h &\leq y + (1-b)M \tag{3} \\ h &\geq y - (1-b)M \tag{4} \end{align} $$

If $b=1$ the constraints (1) and (2) are fulfilled while (3) and (4) enforce $h = y$. If $b=0$ the constraints (3) and (4) are fulfilled while (1) and (2) enforce $h=0$.

$\endgroup$
1
  • 1
    $\begingroup$ As long as you are generalizing, maybe it would be better to assume $L\le y \le U$. $\endgroup$
    – RobPratt
    Apr 11 at 13:58

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