DNF constraint in integer linear programming

Question

I have the following logical constraint which I am having difficulty to put into an equation (or set of equations):

$((x = 1 \text{ AND } y = 1 \text{ AND } z = 1) \text{ OR } (w = 0 \text{ AND } s = 0 \text{ AND } t = 0)) \text{ OR } ((x = 0 \text{ AND } y = 0 \text{ AND } z = 0) \text{ OR } (w=1 \text{ AND } s=1 \text{ AND } t=1))$

One can assume that all the variables are binary.

Thanks.

Answer 1

The logical proposition $$(x \land y \land z) \lor (\neg w \land \neg s \land \neg t) \lor (\neg x \land \neg y \land \neg z) \lor (w \land s \land t)$$ can be rewritten in conjunctive normal form as $$(\neg s\lor w\lor \neg x\lor z)\land(\neg s\lor w\lor x\lor \neg y)\land(\neg s\lor w\lor y\lor \neg z)\land(s\lor \neg t\lor \neg x\lor z)\land(s\lor \neg t\lor x\lor \neg y)\land(s\lor \neg t\lor y\lor \neg z)\land(t\lor \neg w\lor \neg x\lor z)\land(t\lor \neg w\lor x\lor \neg y)\land(t\lor \neg w\lor y\lor \neg z),$$ which yields linear constraints \begin{align} 1- s+ w+ 1- x+ z&\ge 1\\ 1- s+ w+ x+ 1- y&\ge 1\\ 1- s+ w+ y+ 1- z&\ge 1\\ s+ 1- t+ 1- x+ z&\ge 1\\ s+ 1- t+ x+ 1- y&\ge 1\\ s+ 1- t+ y+ 1- z&\ge 1\\ t+ 1- w+ 1- x+ z&\ge 1\\ t+ 1- w+ x+ 1- y&\ge 1\\ t+ 1- w+ y+ 1- z&\ge 1 \end{align} More simply: \begin{align} s- w+ x- z&\le 1\\ s- w- x+ y&\le 1\\ s- w- y+ z&\le 1\\ -s+ t+ x- z&\le 1\\ -s+ t- x+ y&\le 1\\ -s+ t- y+ z&\le 1\\ -t+ w+ x- z&\le 1\\ -t+ w-x+ y&\le 1\\ -t+ w- y+ z&\le 1 \end{align}

Answer 2

HINT

If you define $S = x+y+z$ then two of your constraints are $S \in \{0,3\}$.

Answer 3

We'll use two facts:

• $uv=0\iff u=0\lor v=0$ provides a natural way to encode $\lor$;
• $(u-v)^2\ge0$, with equality iff $u=v$.

Defining $f(a,\,b,\,c):=(a-b)^2+(b-c)^2\color{blue}{+a^2(1-a)^2}$ (the blue term isn't needed if all variables are guaranteed to be $0$ or $1$, as this question seems to say), you could try $f(x,\,y,\,z)f(s,\,t,\,w)=0$.