Let $i$ and $j$ be two binary variables.
How can I express $i \neq j$ as a linear constraint?
Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.Sign up to join this community
@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 $$