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:
where should be an absolute value of
. We know that
is at least
and we use the formula above to enforce the equality. Effectively, we want to say that
is either equal to
or
We know that this is very dangerous as it implicitly requires to be at least
. However, we don’t need to compare numbers precisely. What we need is a formula which will not allow for
to be greater than
. Let’s introduce this unreliable comparison:
if then
must be one. However, if
then
is already non-positive so
can be either zero or one.
However, important part for us is that if then
will be one. So now we can do two comparisons:
If then both comparisons would yield true which in turn would violate the constraint. Since we know that
is at least
then there is no other way as to set
. 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.