XNOR as linear inequalities

Boolean expressions are found in many MIP models. AND and OR are the most common. When we have an expression like \(x {\bf{\ and\ }} y\) or \(x {\bf{\ or\ }} y\), where all variables are binary, we typically reformulate this as a set of inequalities. XOR is a bit more exotic, but I have never seen a usage for XNOR. Until now [1].

As this is about boolean logic, in the discussion below all variables \(x\), \(y\), \(z\) are binary.   

AND  

First let's cover some more well-known boolean expression: AND and OR. The AND operator can be defined by a so-called truth-table [2]:

 

\(x\)	\(y\)	\(x{\bf\ and\ }y\)
0	0	0
0	1	0
1	0	0
1	1	1

The construct \(z = x {\bf\ and \ }y\) can be written as three inequalities: \[\begin{align} &z \le x \\ & z \le y \\ & z \ge x+y-1\end{align}\] These constraints can be interpreted as: \[\begin{align} &z \le x &&:&&x=0\implies z=0 \\ & z \le y &&:&&  y=0\implies z=0 \\ & z \ge x+y-1 &&:&& x=y=1 \implies z=1\end{align}\] Depending on the objective or the constraint, we may drop the \(\le\) or \(\ge\) constraints. 

OR

The OR operator works like:

 

\(x\)	\(y\)	\(x{\bf\ or\ }y\)
0	0	0
0	1	1
1	0	1
1	1	1

The inequalities that describe this are: \[\begin{align} & z \ge x \\ & z \ge y \\ & z \le x+y \end{align}\] These constraints implement the implications  \[\begin{align} &x=1 \implies z=1 \\ & y=1 \implies z=1 \\ & x=y=0 \implies z=0\end{align}\]

XOR

Before working on XNOR, let's do XOR (exclusive or). We need:

 

\(x\)	\(y\)	\(x{\bf\ xor\ }y\)
0	0	0
0	1	1
1	0	1
1	1	0

This is a bit more difficult. We need four inequalities: \[\begin{align} & z \le x+y \\& z\ge y-x \\ & z\ge x-y  \\ & z \le 2-x-y\end{align}\] They implement the implications: \[\begin{align} & x=y=0 \implies z=0 \\ & x=0,y=1 \implies z=1 \\ & x=1,y=0 \implies z=1 \\ & x=y=1 \implies z=0 \end{align}\]

XNOR

XNOR is an XOR followed by a NOT: \[z = x {\bf\ xnor \ } y = {\bf not\ }(x {\bf\ xor \ } y)\] I.e.

 

\(x\)	\(y\)	\(x{\bf\ xor\ }y\)	\(x{\bf\ xnor\ }y\)
0	0	0	1
0	1	1	0
1	0	1	0
1	1	0	1

Obviously, we can write this as:  \[\begin{align} & 1-z \le x+y \\& 1-z\ge y-x \\ & 1-z\ge x-y  \\ & 1-z \le 2-x-y\end{align}\] We just used the inequalities from the XOR discussion and replaced \(z\) by \(1-z\) (this is corresponding to \({\bf not\ }z\)). Totally optionally, we can re-arrange this as:  \[\begin{align} & z \ge 1-x-y \\& z\le 1+x-y \\ & z\le 1-x+y \\ & z \ge x+y-1\end{align}\] Again, we can easily interpret these constraints as: \[\begin{align} & x=y=0 \implies z=1 \\ & x=0,y=1\implies z=0 \\ & x=1,y=0\implies z=0 \\ & x=y=1 \implies z=1\end{align}\]

Notes

Quadratic models can have these operations in disguise. E.g. \(x\cdot y\) is the same as \(x {\bf\ and\ }y\) for binary variables \(x,y\). \((x-y)^2 \) is the same as  \(x {\bf\ xor\ }y\).

In many cases we can drop the \(\le\) or \(\ge\) constraints. Some examples are:

• An objective like \(\max \sum_{i,j} (x_i {\bf\ xor\ }x_j)\)  allows us to write [3]: \[\begin{align}\max&\sum_{i,j} z_{i,j} \\ & z_{i,j} \le x_i+x_j \\ & z_{i,j} \le 2- x_i-x_j  \\& x_i, z_{i,j} \in \{0,1\}\end{align}\]
• A constraint like \(\sum_{i,j} x_i\cdot x_j \le a\) can be written as: \[\begin{align}&\sum_{i,j} z_{i,j} \le a\\ & z_{i,j} \ge x_i+x_j-1 \\ &  x_i,z_{i,j} \in \{0,1\}\end{align}\]

In most cases, we can relax \(z\) to be continuous between 0 and 1. Modern solvers may like binary variables better. They may even convert a continuous variable \(z\) back into a binary one. 

References

1. Modeling XNOR in Pyomo, https://stackoverflow.com/questions/72788382/modeling-xnor-in-pyomo
2. Truth Table, https://en.wikipedia.org/wiki/Truth_table
3. MAX CUT, https://yetanothermathprogrammingconsultant.blogspot.com/2022/06/max-cut.html