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
I am trying to linearize the following expression without using the Big-M formulation, but I cannot convert it. I am willing to know if there exists an efficient way to do that?
$$ Iff \quad (w=1) \Longleftrightarrow (x \Longleftrightarrow y)$$
where, $x$, $y$, and $w$ are binary variables?
One possible way to linearize such a constraint would be by dividing this expression into four parts and then linearizing each of which separately.
$$ Iff \quad (w=1) \rightarrow (x \rightarrow y) \quad (\text{Part-1})$$ $$ Iff \quad (w=1) \rightarrow (y \rightarrow x) \quad (\text{Part-2})$$ $$ Iff \quad (x \rightarrow y) \rightarrow (w=1) \quad (\text{Part-3})$$ $$ Iff \quad (y \rightarrow x) \rightarrow (w=1) \quad (\text{Part-4})$$
Then, the first one can be translated as: $$ (w) \rightarrow (\lnot x \lor y)$$ $$ \lnot(w) \lor (\lnot x \lor y)$$ $$ \lnot w \lor \lnot x \lor y$$ $$ (1-w) + (1-x) + y \geq 1 \quad (\text{Part-1})$$
The second part would be the same as the one and the result is: $$ (1-w) + (1-y) + x \geq 1 \quad (\text{Part-2})$$
The third part can be linearized as: $$ (\lnot x \lor y) \rightarrow (w)$$ $$ \lnot (\lnot x \lor y) \lor(w)$$ $$ (x \land \lnot y) \lor (w)$$ $$ (x \lor w) \bigwedge (\lnot y \lor w)$$ $$ (x + w \geq 1) \bigwedge ((1-y) + w \geq 1) \quad (\text{Part-3})$$ $$ (y + w \geq 1) \bigwedge ((1-x) + w \geq 1) \quad (\text{Part-4})$$
Also, the third and fourth parts can already be written as: $$ \lnot ((\lnot x \lor y) \land (\lnot y \lor x)) \lor w$$ $$ (x + y + w \geq 1) \bigwedge (w \geq x + y - 1) \quad (\text{Part-(3,4)})$$
@A.Omidi gave a nice derivation using conjunctive normal form. In this case, the big-M approach with $M=1$ yields the same formulation: $$w = 1 \implies x=y$$ can be enforced via $$-(1-w) \le x-y \le 1-w,$$ and $$w = 0 \implies x+y=1$$ can be enforced via $$-w \le x+y-1 \le w.$$
An alternative approach is to introduce a binary decision variable $v$ and impose a single equality constraint $$x+y=2v+1-w.$$
