# Standard linearization

The standard way to linearize the product of two binary variables $LaTeX: x$ and $LaTeX: y$ is to replace $LaTeX: xy$ with a continuous variable $LaTeX: w$ and add four linear inequalities as auxiliary constraints:

$LaTeX: \begin{array}{ll} & w \le x, \\ & w \le y, \\ & w \ge x + y - 1, \\ and & w \ge 0. \end{array}$

Collectively, these imply $LaTeX: w = xy$ for all binary values of $LaTeX: x$ and $LaTeX: y$. This can be generalized for the product of binary variables $LaTeX: x_j$ for all $LaTeX: j$ in some index set $LaTeX: J$ by replacing $LaTeX: \textstyle \prod_{j \in J} x_j$ with a continuous variable $LaTeX: w$ and adding $LaTeX: |J| + 2$ auxiliary constraints:

$LaTeX: \begin{array}{ll} & w \le x_j \mbox{ for all } j \in J, \\ & w \ge \sum_{j \in J} x_j - (|J| - 1), \\ and & w \ge 0. \end{array}$