# $i \neq j$ as a linear constraint where variables are binary

Let $$i$$ and $$j$$ be two binary variables.

How can I express $$i \neq j$$ as a linear constraint?

• $i+j=1$ ........... – user3680510 Jan 15 at 22:32
• in fact, i want to prevent both to be 1 at the same time. how can I do this? – DSPinfinity Jan 15 at 22:36

@user3680510 gave the correct answer in a comment. Here's a way to derive it via conjunctive normal form: $$i \not= j \\ (i \implies \lnot j) \land (\lnot i \implies j) \\ (\lnot i \lor \lnot j) \land (i \lor j) \\ (1 - i + 1 - j \ge 1) \land (i + j \ge 1) \\ (i + j \le 1) \land (i + j \ge 1) \\ i + j = 1$$

To prevent both to be 1 at the same time: $$\lnot(i \land j) \\ \lnot i \lor \lnot j \\ 1 - i + 1 - j \ge 1 \\ i + j \le 1$$

• in fact, i want to prevent both to be 1 at the same time. how can I do this? – DSPinfinity Jan 15 at 22:40
• I updated my answer. – RobPratt Jan 15 at 22:41