Processing math: 100%

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 and y or x 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]:
 
xyx and y
000
010
100
111

The construct z=x and y can be written as three inequalities: zxzyzx+y1 These constraints can be interpreted as: zx:x=0z=0zy:y=0z=0zx+y1:x=y=1z=1 Depending on the objective or the constraint, we may drop the or constraints. 

OR


The OR operator works like:

 
xyx or y
000
011
101
111

The inequalities that describe this are: zxzyzx+y These constraints implement the implications  x=1z=1y=1z=1x=y=0z=0


XOR


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

 
xyx xor y
000
011
101
110

This is a bit more difficult. We need four inequalities: zx+yzyxzxyz2xy They implement the implications: x=y=0z=0x=0,y=1z=1x=1,y=0z=1x=y=1z=0

XNOR


XNOR is an XOR followed by a NOT: z=x xnor y=not (x xor y) I.e.

 
xyx xor yx xnor y
0001
0110
1010
1101

Obviously, we can write this as:  1zx+y1zyx1zxy1z2xy We just used the inequalities from the XOR discussion and replaced z by 1z (this is corresponding to not z). Totally optionally, we can re-arrange this as:  z1xyz1+xyz1x+yzx+y1 Again, we can easily interpret these constraints as: x=y=0z=1x=0,y=1z=0x=1,y=0z=0x=y=1z=1


Notes


Quadratic models can have these operations in disguise. E.g. xy is the same as x and y for binary variables x,y. (xy)2 is the same as  x xor y.

In many cases we can drop the or constraints. Some examples are:
  • An objective like maxi,j(xi xor xj)  allows us to write [3]: maxi,jzi,jzi,jxi+xjzi,j2xixjxi,zi,j{0,1}
  • A constraint like i,jxixja can be written as: i,jzi,jazi,jxi+xj1xi,zi,j{0,1}
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

    ReplyDelete