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

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

## No comments:

## Post a Comment