ILP Part 74 — Absolute value for real numbers

This is the seventieth 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 know how to calculate absolute value and how to compare real numbers.

The original formula uses comparisons:

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

where $r$ should be an absolute value of $a$ . We know that $r$ is at least $|a|$ and we use the formula above to enforce the equality. Effectively, we want to say that $r$ is either equal to $a$ or $-a$

We know that this is very dangerous as it implicitly requires $x + a$ to be at least $\epsilon$ . However, we don’t need to compare numbers precisely. What we need is a formula which will not allow for $r$ to be greater than $|a|$ . Let’s introduce this unreliable comparison:

$0 \le r - a - Kx$

if $a < r$ then $x$ must be one. However, if $a \ge r$ then $r - a$ is already non-positive so $x$ can be either zero or one.

However, important part for us is that if $a < r$ then $x$ will be one. So now we can do two comparisons:

$\left(r \stackrel{?}{\~>} a\right) \vee \left(r \stackrel{?}{\~>} -a\right) = 1$

If $r > |a|$ then both comparisons would yield true which in turn would violate the constraint. Since we know that $r$ is at least $|a|$ then there is no other way as to set $r = |a|$ . This works because solver can choose any result for unreliable comparisons.

This can be used for integer values as well. We can effectively calculate absolute value without any comparisons (which break the model for real numbers). Same goes for maximum and minimum, we can calculate these in a safe manner.