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$?
1 Answer
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$.
-
1$\begingroup$ As long as you are generalizing, maybe it would be better to assume $L\le y \le U$. $\endgroup$– RobPrattApr 11, 2021 at 13:58