Linear program with $\pm 1$ constraints

Question

I am trying to formulate a constraint as follows ($X, Y, Z$ are either $-1$ or $1$):

If $Z$ and $Y$ both equal $-1$, then $X$ must be $1$. But, if either $Z$ or $Y$ are not $-1$, then $X$ can be $-1$ or $1$.

I came up with $Z\cdot Y \le X$, but that limits $X$ to $1$ if both $Z$ and $Y$ are $1$ ($X$ can be $0$ if both are $1$).

Any advice on a more accurate constraint?

Thank you.

Answer 1

Note: If you're trying to keep a linear program, do not add constraints of the form ZY

My solution: $-3(Y+Z)\leq 5+X$

I am not sure if a better solution exists, however!

Answer 2

There is one invalid case in your problem $(z, y, x) = (-1, -1, -1)$. You can use $4z+2y+x \geq -5$.

$$(z, y, x) \in \{(-1, -1, 1), (-1, 1, -1), (1, -1, -1), (1, 1, -1), (-1, 1, 1), (1, -1, 1), (1, 1, 1)\}$$

Answer 3

Let $X=2x-1,Y=2y-1,Z=2z-1$, where $x,y,z\in\{0,1\}$. Then you want to model $\neg z \land \neg y \implies x$. Rewrite in conjunctive normal form to obtain a linear constraint: $$\begin{equation} \neg (\neg z \land \neg y) \lor x \\ z \lor y \lor x \\ z+y+x\ge 1\\ (Z+1)/2+(Y+1)/2+(X+1)/2\ge 1\\ Z+Y+X\ge -1 \end{equation}$$