4
$\begingroup$

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?

$\endgroup$

2 Answers 2

5
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ Thank you @RobPratt, for your suggestion. $\endgroup$
    – Mr. Blue
    Mar 12, 2023 at 5:15

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.