How can I apply the McCormick Envelopes to the product of two binary variables?

287 Views Asked by At

I've seen the McCormick envelopes applied many times to the product of two continuous variables, but I can't seem to find when both of them are binaries. Also, I applied the restrictions as described bellow, and they don't work because they don't make sense when both of them are 1.

the restrictions: $$ \begin{align*} w_{i j} &\geq x_{i}^{L} \cdot x_{j} + x_{i} \cdot x_{j}^{L} - x_{i}^{L} \cdot x_{j}^{L}\\ w_{i j} &\geq x_{i}^{U} \cdot x_{j} + x_{i} \cdot x_{j}^{U} - x_{i}^{U} \cdot x_{j}^{U}\\ w_{i j} &\leq x_{i}^{U} \cdot x_{j} + x_{i} \cdot x_{j}^{L} - x_{i}^{U} \cdot x_{j}^{L}\\ w_{i j} &\leq x_{i} \cdot x_{j}^{U} + x_{i}^{L} \cdot x_{j} - x_{i}^{L} \cdot x_{j}^{U}\\ x^{L} &\leq x \leq x^{U} \qquad~ w^{L} \leq w \leq w^{U} \end{align*} $$

1

There are 1 best solutions below

1
On BEST ANSWER

Substituting $0$ for $x^L$ and $1$ for $x^U$ yields: \begin{align} w_{i j} &\ge 0 \\ w_{i j} &\ge x_j + x_i - 1 \\ w_{i j} &\le x_j \\ w_{i j} &\le x_i \end{align} This is the usual linearization of $w_{ij} = x_i x_j$. See https://or.stackexchange.com/questions/37/how-to-linearize-the-product-of-two-binary-variables