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