3
$\begingroup$

What constraints would you write to ensure that if $x = 1$ then $y = 0$ where $x, y$ are binary variables?

Until now I only learnt how to build the constraint with 3 binary variables, therefore the difficulty level of this task is very high for me.

$\endgroup$
1

1 Answer 1

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ what is the meaning of x + y <= 1 ? @RobPratt $\endgroup$
    – overboxed
    Commented Nov 23, 2022 at 10:06
  • $\begingroup$ @overboxed It is a linear inequality constraint that the binary decision variables $x$ and $y$ are required to satisfy. This constraint prevents $(x,y)=(1,1)$, which is the only solution that would violate the desired implication. $\endgroup$
    – RobPratt
    Commented Nov 23, 2022 at 13:33

Your Answer

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

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