3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've actually managed to model a XOR using the Big-M method, but I cannot get my head around the OR. $\endgroup$ – Marcello S Jul 14 '17 at 20:12
  • $\begingroup$ Can you express "$x=1$ or $y=1$"? $\endgroup$ – Yuval Filmus Jul 14 '17 at 20:23
  • $\begingroup$ 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)? $\endgroup$ – Marcello S Jul 14 '17 at 20:28
  • $\begingroup$ Try next "$x+y=1$ or $z=1$". $\endgroup$ – Yuval Filmus Jul 14 '17 at 20:32
  • $\begingroup$ I think that should do it: z <= x + y ; z + x + y > 0 $\endgroup$ – Marcello S Jul 14 '17 at 20:43
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.