## Tuesday, February 21, 2017

### Multiplication of binary with continuous variable between zero and one

A small tidbit.

The standard linearization for the multiplication of two binary variables $$z=x \cdot y$$ with $$x,y \in \{0,1\}$$ is:

 \boxed{\begin{align}&z\le x\\&z \le y\\& z\ge x+y-1\\&z \in \{0,1\}\end{align}}

What about if $$y$$ is continuous between zero and one, $$y\in[0,1]$$ (while $$x$$ remains a binary variable)? In that case we can use the formulation in (1) where we consider a continuous variable $$y \in [y^{lo},y^{up}]$$:

 \boxed{\begin{align}&\min\{0,y^{lo}\} \le z \le \max\{0,y^{up}\} \\ &y^{lo} \cdot x \le z \le y^{up} \cdot x \\ &y − y^{up} \cdot (1 − x) \le z \le y − y^{lo} \cdot (1 − x)\end{align}}

When we plug in $$y^{lo}=0$$ and $$y^{up}=1$$, we end up with the same thing:

 \boxed{\begin{align}&z\le x\\&z \le y\\& z\ge x+y-1\\&z \in [0,1]\end{align}}

We can easily verify the correctness by checking what happens when $$x=0$$ or $$x=1$$:

 \begin{align} &x=0 & \implies & \begin{cases} z\le 0\\ z \le y &\text{(NB)}\\ z \ge y-1 &\text{(NB)} \\ z \in [0,1] \end{cases} & \implies & z=0 \\ &x=1 & \implies & \begin{cases} z\le 1 & \text{(NB)}\\ z \le y \\ z \ge y \\ z \in [0,1] \end{cases} & \implies & z=y \end{align}

where $$\text{NB}$$ means non-binding by which I mean we can ignore this constraint.

##### References
1. Multiplication of a continuous and a binary variable, http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-continuous-and-binary.html