2
$\begingroup$

I am trying to solve the following task: If $x=1$ or $y=0$ then $z=0$

My approach:

If $z=0$ then $x+y \le 2 + Mz \implies x+y \le 2+2z \quad$ where $M = 2$

If $z=1$ then $x+y=1 \\ \implies x+y \le 1, \quad x+y \ge 1 - M(1-z) \\ \implies x+y \ge z$

where $M = 1$

I already tried to add the constraint: $y-x \ge 0$ to ensure that combination $x=1, y=0, z=1$ should be satisfied and combination $x=1, y=0, z=1$ should be not satisfied.

But then the combination $x=1, y=0, z=0$ isn’t satisfied, although it should be.

In 1 combination the sum of $x+y = 2$.

I would be grateful for any hints regarding the task or showing where my approach is wrong.

$\endgroup$

1 Answer 1

6
$\begingroup$

Via conjunctive normal form, $$ (x \lor \lnot y) \implies \lnot z \\ \lnot (x \lor \lnot y) \lor \lnot z \\ (\lnot x \land y) \lor \lnot z \\ (\lnot x \lor \lnot z) \land (y \lor \lnot z) \\ ((1 - x) + (1 - z) \ge 1) \land (y + (1 - z) \ge 1) \\ (x + z \le 1) \land (y \ge z) $$

$\endgroup$
5
  • $\begingroup$ is there any problem to write $x+z \leq 1$ as $x+z = 1$? $\endgroup$
    – A.Omidi
    Nov 26, 2022 at 9:44
  • 1
    $\begingroup$ @A.Omidi That is too strong. For example, it would mistakenly cut off $(x,y,z)=(0,0,0)$. $\endgroup$
    – RobPratt
    Nov 26, 2022 at 14:31
  • $\begingroup$ many thanks. 🙏 $\endgroup$
    – A.Omidi
    Nov 26, 2022 at 16:03
  • $\begingroup$ The conjunctive normal form derivation is a powerful and general approach, but it can be obscure in simple cases. Here, the correctness of the linear reformulation is clearer if you write it as $z\leq (1-x)$ and $z\leq y$. $\endgroup$
    – 4er
    Apr 2 at 15:24
  • $\begingroup$ @4er Indeed, your rewrite arises immediately from the contrapositive $z \implies (\lnot x \land y)$. $\endgroup$
    – RobPratt
    Apr 2 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.