## Wednesday, June 29, 2022

### 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$$
000
010
100
111

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$$
000
011
101
111

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$$
000
011
101
110

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$$
0001
0110
1010
1101

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 comment:

1. Your readers might be interested in knowing that all these formulations arise somewhat automatically from conjunctive normal form. For example, see https://or.stackexchange.com/a/473/500