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

Last time we defined formulas to compare values. Today we are going to use them to calculate absolute value, maximum, and minimum functions.

Table of Contents

Absolute value

We will start with absolute value. Just like in previous part, we need to know the maximum possible value of a variable denoted as $k$ .

Variables

We want to use the following variables:

$\begin{gather*} a \in \mathbb{Z} \\ \left|a\right| \le k\\ x \in \mathbb{Z_+} \cup \{0\}\\ x = \left|a\right| \end{gather*}$

Basically, we have one variable called $a$ . We don’t know whether this variable is positive or negative. We also want to declare variable $x$ which will be equal to absolute value of $a$ . So for non-negative $a$ it will be equal to $a$ , however, for negative $a$ it will have its value negated.

Intuition and final formula

We will start with two simple constraints. We want $x$ to be absolute value of $a$ , so we know for sure that $x$ must be:

$\begin{gather*} x \ge a\\ x \ge -a \end{gather*}$

This can be interpreted as: “ $x$ must be on the right side of $\left|a\right|$ on the number line. However, this is not enough because $x$ might not be equal to $\left|a\right|$ .
Now we can use geometric interpretation of absolute value of a number. It is a number’s distance from origin. We want $x$ to have the same distance and to achieve this we need to add the following constraints:

$\left(x + a \stackrel{?}{=} 0\right) \vee \left(x - a \stackrel{?}{=} 0\right) = 1$

This line basically says: either the sum of $a$ and $x$ is zero or the sum of negated $a$ and $x$ is zero. Here we use relational operators defined in previous part and this is the place where we need to know the upper bound of $a$ ‘s value.

Maximum, minimum

Using similar intuition we can define maximum and minimum functions. We start with the following variables:

$\begin{gather*} a,b \in \mathbb{Z} \\ \left|a\right|, \left|b\right| \le k\\ M,m \in \mathbb{Z}\\ M = \max(a,b)\\ m = \min(a,b) \end{gather*}$

First, we want $M$ to be “on the right side” of $a$ and $b$ :

$\begin{gather*} M \ge a\\ M \ge b \end{gather*}$

Similarly, we want $m$ to be “on the left side”:

$\begin{gather*} m \le a\\ m \le b \end{gather*}$

And now the final piece: we want the distance between $a$ and $b$ to be the equal to the distance between $m$ and $M$ :

$\left|a - b\right| = M - m$

We need to use the absolute value only on the left side because we know that $M \ge m$ .
However, this will not work. In previous part we defined and used $K=2k+1$ and we showed why it is important to define it this way. However, our absolute value function uses relational operators, and these assume that their arguments are not greater than $k$ . But for $a = k$ and $b = -k$ we break this constraint. There are two possible solutions:

Solution 1

We can change the definition of $K$ to $2\left(2k + 1\right)$ . This will work but it has one drawback: imagine that our solver is able to perform calculations on 32-bit integers. Because we need to be able to represent $K$ using 32 bits, we are effectively reducing the size of the rest of our variables. This might be painful.

Solution 2

We might want to change the last constraint to:

$\left|\frac{a-b}{2}\right| = M-m$

In theory, this should work. However, imagine the situation when $a-b$ is odd. We need to represent the result of division using floating point values and this might cause some problems with representation errors with more sophisticated calculations. However, using this approach we do not reduce the size of our variables as with the previous solution.

Summary

We have defined three useful functions. In next parts we will see that they might look trivial, but they are really powerful and we will use them to define much more complicated calculations. See you next time.