1
$\begingroup$

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.

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

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}

$\endgroup$
0
$\begingroup$

HINT

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

$\endgroup$
0
$\begingroup$

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

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