# DNF constraint in integer linear programming

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.

• hi @gt6989b yes, it is a typo, it is updated! – Thomas Moore Oct 24 '19 at 16:18
• @RodrigodeAzevedo Binary Integer Linear Programming or BILP is a very big area of operations research! – Thomas Moore Oct 24 '19 at 17:05
• @RodrigodeAzevedo chill dude. It is all linear programming. – Thomas Moore Oct 24 '19 at 17:34

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}
If you define $$S = x+y+z$$ then two of your constraints are $$S \in \{0,3\}$$.
• $$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$$.