Standard linearization

From Glossary

Jump to: navigation, search

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}


Views
Personal tools