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]:
x | y | x and y |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
The construct z=x and y can be written as three inequalities: z≤xz≤yz≥x+y−1 These constraints can be interpreted as: z≤x:x=0⟹z=0z≤y:y=0⟹z=0z≥x+y−1:x=y=1⟹z=1 Depending on the objective or the constraint, we may drop the ≤ or ≥ constraints.
OR
The OR operator works like:
The inequalities that describe this are: z≥xz≥yz≤x+y These constraints implement the implications x=1⟹z=1y=1⟹z=1x=y=0⟹z=0
XOR
Before working on XNOR, let's do XOR (exclusive or). We need:
This is a bit more difficult. We need four inequalities: z≤x+yz≥y−xz≥x−yz≤2−x−y They implement the implications: x=y=0⟹z=0x=0,y=1⟹z=1x=1,y=0⟹z=1x=y=1⟹z=0
XNOR
XNOR is an XOR followed by a NOT: z=x xnor y=not (x xor y) I.e.
x | y | x xor y | x xnor y |
---|
0 | 0 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
Obviously, we can write this as: 1−z≤x+y1−z≥y−x1−z≥x−y1−z≤2−x−y We just used the inequalities from the XOR discussion and replaced z by 1−z (this is corresponding to not z). Totally optionally, we can re-arrange this as: z≥1−x−yz≤1+x−yz≤1−x+yz≥x+y−1 Again, we can easily interpret these constraints as: x=y=0⟹z=1x=0,y=1⟹z=0x=1,y=0⟹z=0x=y=1⟹z=1
Notes
Quadratic models can have these operations in disguise. E.g. x⋅y is the same as x and y for binary variables x,y. (x−y)2 is the same as x xor y.
In many cases we can drop the ≤ or ≥ constraints. Some examples are:
- An objective like max∑i,j(xi xor xj) allows us to write [3]: max∑i,jzi,jzi,j≤xi+xjzi,j≤2−xi−xjxi,zi,j∈{0,1}
- A constraint like ∑i,jxi⋅xj≤a can be written as: ∑i,jzi,j≤azi,j≥xi+xj−1xi,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
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