# The linearization of the (Iff-and-only-Iff) expression

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)})$$

• +1 for conjunctive normal form, which in this case turns out to yield the same formulation as the big-M approach. Commented Mar 11, 2023 at 12:31
• @RobPratt, Thanks a lot for your help and hints. Commented Mar 11, 2023 at 12:33

@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.$$

• Thank you @RobPratt, for your suggestion. Commented Mar 12, 2023 at 5:15