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

  • $\begingroup$ 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$) $\endgroup$ – Milo Brandt Nov 21 '19 at 20:09
  • $\begingroup$ @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. $\endgroup$ – 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}

  • $\begingroup$ 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 $\endgroup$ – Haleh Nov 22 '19 at 14:28
  • $\begingroup$ But you said that $x=0 \implies y=1$. $\endgroup$ – Rob Pratt Nov 22 '19 at 15:06
  • $\begingroup$ You're right. My bad. I was looking at $x + \neg y = 0$ $\endgroup$ – Haleh Nov 22 '19 at 15:11

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.