# Model disjunction in a $\{0,1\}$ integer linear program

How can I model logical OR as an integer linear program?

$$(y_3 + y_4 + y_5 + y_6 = 2) \lor (y_2 = 1)$$

where $y_i \in \{0, 1\}$, $1$ = True and $0$ = False.

• I've actually managed to model a XOR using the Big-M method, but I cannot get my head around the OR. – Marcello S Jul 14 '17 at 20:12
• Can you express "$x=1$ or $y=1$"? – Yuval Filmus Jul 14 '17 at 20:23
• That should be: x + y > 0 , right? I think the difficulty lies in the (y3+y4+y5+y6=2). Do I need an extra variable that expresses if (y3+y4+y5+y6=2)? – Marcello S Jul 14 '17 at 20:28
• Try next "$x+y=1$ or $z=1$". – Yuval Filmus Jul 14 '17 at 20:32
• I think that should do it: z <= x + y ; z + x + y > 0 – Marcello S Jul 14 '17 at 20:43

Let's assume that all variables are Boolean (constrained to $\{0,1\}$). Here is how to encode the constraint "$x+y=1$ or $z=1$". Presumably you can extend this.

\begin{align*} &x+y+u-v = 1 \\ &z+w = 1 \\ &w+u+v \leq 1 \end{align*}

If $x+y = 1$ then we take $u=v=0$ and $w=1-z$.

If $z = 1$ and $x+y = 0$ then we take $u=1$, $v=0$ and $w=0$.

If $z = 1$ and $x+y = 2$ then we take $u=0$, $v=1$ and $w=0$.

This shows that these equations are solvable when $x+y=1$ and when $z=1$.

Conversely, suppose that these equations are solvable, and so at most one of $w,u,v$ is non-zero. If $w = 0$ then $z = 1$. Otherwise, $u=v=0$ and so $x+y = 1$.

For simplicity let $Y = y_3+y_4+y_5+y_6$. We can rewrite you requirement as $( (Y \geq 2) \land (Y \leq 2) ) \lor ((y_2 \geq 1) \land (y_2 \leq 1))$. Introduce a binary variable $z_1$ to detect if $(Y \geq 2)$ using $M$ variables. Similarly introduce $z_2$ to detect if $(Y \leq 2)$. Do the same for the other inequalities and call them say $z_3, z_4$. Now introduce binary variable $z_5 = z_1 \land z_2$ (this can be done using Fortet's linearization without $M$ variables), similarly $z_6 = z_3 \land z_4$. Lastly constrain $z_5 + z_6 \geq 1$.