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.
Let’s assume that we have two integer variables: and . We want to know whether is greater than and we want to store this information in variable . 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.
First lets define variables:
We have two integer variables, both of them not greater than arbitrary defined number named . Since we will probably solve our models using computers, we assume that is close to some power of two. We also define constant , which we will use later. Finally, we define binary variable , 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:
which means that is equal to one if and only if is greater than , otherwise is equal to zero. We can achieve this using the following constraints:
When is greater than , then is negative and must be equal to one. Otherwise we would receive which cannot happen because of the left inequality. However, when is not greater than , their difference is non-negative and has to be zero.
We use value greather than because for case when and , their difference . In that case we obtain:
Now imagine that . We get:
On the other hand, , so inequality has no solutions.
We have define only one relational operator, but now we are able to use it to define others. That is:
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.