This is the fourth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

We have already seen how to define Boolean algebra. We also know how to multiply variables or calculate division, remainder, powers, and roots. Today we are going to compare variables.

Table of Contents

Idea

Let’s assume that we have two integer variables: $a$ and $b$ . We want to know whether $a$ is greater than $b$ and we want to store this information in variable $x$ . We do not want to enforce this constraint, we only want to know the result of the comparison.
As we will see in later parts of this series, such a knowledge will allow us to calculate more sophisticated mathematical functions, like maximum or absolute value. But today we need to start with basics.

Basics

First lets define variables:

$\begin{gather*} a, b \in \mathbb{Z} \\ \left|a\right|, \left|b\right| \le k \\ k = 2^n - 1, n \in \mathbb{N} \\ K = 2\cdot k + 1\\ x \in \{0, 1\} \end{gather*}$

We have two integer variables, both of them not greater than arbitrary defined number named $k$ . Since we will probably solve our models using computers, we assume that $k$ is close to some power of two. We also define constant $K$ , which we will use later. Finally, we define binary variable $x$ , which will hold the result of the comparison.

Greater than comparison

Now we are going to implement greater than operator. We want to define the following:

$x = a \stackrel{?}{>}b$

which means that $x$ is equal to one if and only if $a$ is greater than $b$ , otherwise $x$ is equal to zero. We can achieve this using the following constraints:

$0 \le b - a + Kx \le K - 1$

When $a$ is greater than $b$ , then $b - a$ is negative and $x$ must be equal to one. Otherwise we would receive $b - a + K\cdot0 < 0$ which cannot happen because of the left inequality. However, when $a$ is not greater than $b$ , their difference $b - a$ is non-negative and $x$ has to be zero.
We use value $K$ greather than $2\cdot k$ because for case when $a = -k$ and $b = k$ , their difference $b-a = k - \left(-k\right) = 2k$ . In that case we obtain:

$0 \le 2k + Kx \le K-1$

Now imagine that $K \le 2k$ . We get:

$2k + Kx \ge 2k + 2kx \ge 2k\left(1+x\right)\ge 2k$

On the other hand, $K-1 \le 2k-1$ , so inequality $2k + Kx \le K-1$ has no solutions.

Other operators

We have define only one relational operator, but now we are able to use it to define others. That is:

$\begin{gather*} a \stackrel{?}{<} b \equiv b \stackrel{?}{>} a\\ a \stackrel{?}{\le}b \equiv \neg \left(a \stackrel{?}{>}b \right)\\ a \stackrel{?}{\ge}b \equiv \neg \left(a \stackrel{?}{<}b \right)\\ a \stackrel{?}{=}b \equiv \left(a \stackrel{?}{\le} b \right) \wedge \left( a \stackrel{?}{\ge} b \right)\\ a \stackrel{?}{\neq}b \equiv \neg \left(\left(a \stackrel{?}{\le} b \right) \wedge \left( a \stackrel{?}{\ge} b \right)\right) \end{gather*}$

Summary

We defined relational operators and now we are able to compare variables. In the next part we will see how to utilize this knowledge to calculate absolute value, maximum, and minimum. These trivial functions are in fact really powerful and we will use them many times in other operators.