# Combination of AND OR in Linear Programming

I have three binary variables: $$x,y,z$$.

I want to define $$U$$ as follows: $$U = x \wedge (y \vee z)$$

Following this, I have already tried defining

$$yz = y \vee z$$

and then, doing

$$U = x \wedge yz$$

But this adds too many variables and constraints to my problem (since $$yz$$ has $$810000$$ variables). Is there any simpler approach for linearizing this?

If it helps, in my problem, when $$x = 0$$, $$y,z=1$$.

• I'm very confused by what you mean by "$yz$ has 810000 variables" or what precisely you mean by linearizing it? Also, if you know two of the variables, there are only two possible inputs remaining - why not just compute cases (or just notice that $0 \wedge ...$ is just $0$) – Milo Brandt Nov 21 '19 at 20:09
• @MiloBrandt I tried to simplify my problem. For my problem, I have 900 of different $y$ and 900 of different $z$. So, the one constraints that I showed with $yz$ is actually 810000 constraints. That's why I need a more concise approach.constraints. – Haleh Nov 21 '19 at 20:16

Rewrite in conjunctive normal form: $$\begin{equation} u \iff (x \land (y \lor z)) \\ [u \implies (x \land (y \lor z))] \land [\neg u \implies \neg (x \land (y \lor z)) \\ [\neg u \lor (x \land (y \lor z))] \land [u \lor \neg (x \land (y \lor z)) \\ [(\neg u \lor x) \land (\neg u \lor y \lor z)] \land [u \lor (\neg x \lor \neg (y \lor z)) \\ [(\neg u \lor x) \land (\neg u \lor y \lor z))] \land [u \lor (\neg x \lor (\neg y \land \neg z)) \\ [(\neg u \lor x) \land (\neg u \lor y \lor z))] \land [(u \lor \neg x \lor \neg y) \land (u \lor \neg x \lor \neg z)) \\ (1-u +x\ge 1) \land (1-u +y +z\ge 1)\land (u+1-x +1-y\ge 1) \land (u +1-x +1- z\ge 1) \\ (u \le x) \land (u \le y +z)\land (u\ge x+y-1) \land (u\ge x+z-1), \end{equation}$$ which is a stronger formulation than @LinAlg.
Similarly, $$(u \iff (x \land (y \lor z))) \land (\neg x \implies (y \land z))$$ leads to $$\begin{equation} (¬u ∨ x) ∧ (¬u ∨ y ∨ z) ∧ (u ∨ ¬x ∨ ¬z) ∧ (u ∨ ¬y ∨ z) ∧ (x ∨ y)\\ (1-u + x \ge 1) ∧ (1-u + y + z \ge 1) ∧ (u +1-x +1-z \ge 1) ∧ (u +1-y + z\ge 1) ∧ (x + y \ge 1)\\ (u \le x) ∧ (u \le y + z) ∧ (u \ge x + z - 1) ∧ (u + z\ge y) ∧ (x + y \ge 1) \end{equation}$$
• Thanks for the thorough response but I can not quite follow why $x + y \ge 1$. I know in my problem, there are cases where $x + y = 0$. Doesn't this make the problem infeasible? @RobPratt – Haleh Nov 22 '19 at 14:28
• But you said that $x=0 \implies y=1$. – Rob Pratt Nov 22 '19 at 15:06
• You're right. My bad. I was looking at $x + \neg y = 0$ – Haleh Nov 22 '19 at 15:11