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

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

ReplyDelete