This is the eighth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra
Today we are going to implement multiple and Greatest Common Divisor (GCD) using ILP. Representations of these functions look very trivial, however, they are in fact a bit difficult in practice. Let’s begin.
First step – multiple
We will start with the following requirement: having variable , we want the variable
to be a multiple of
. This means that for the variables
we want
to be a divisor of
. For instance, for
we want
to be equal
, or
, or
, or
, or
, or something else (I hope you get the rule). It is in fact easy using helper variable. The formula is:
We already know how to multiply negative values so we are able to calculate this. Of course we need to set upper bound for variables.
Greatest Common Divisor
Now we are going to implement GCD. As you remember from school, greatest common divisor is a divisor with maximum possible value. We will now use only non-negative variables since GCD is usually defined only for them.
First part – any common divisor
Let’s start with first approach: for variables we would like to define
:
This works only partially. For instance, for we might get
(which is fine), but we might also get
. The latter value fulfills the constraints but it is not the value we are looking for because we want to find the greatest possible value.
Second part – greatest common divisor
To make sure that we get GCD we will use Bézout’s identity. It says that we can represent every multiple of as
. We can add this formula to the previously defined and get the following:
This works as follows: first we define that and
are both multiple of
. This means that
is any common divisor and is not greater than GCD of
and
. The last part says that
is a multiple of GCD of
and
. Since
is a positive variable, the only value fulfilling all the requirements is
!
Problems with the implementation
The formula for GCD looks very trivial, however, there are problems with this approach. First, and
might be very big (much bigger than
and
). Because we need to know the upper bound of values, we need to be very careful what we are going to calculate. What’s more, this is very difficult to solve and many solvers are not capable of doing that. I have checked Gurobi, CPLEX, LpSolve, Microsoft Solver Foundation, and SCIP, and in fact I was able to calculate GCD of very small numbers only (less than
). For bigger values the solvers were returning incorrect results or even saying that there is no solution. So in theory it works, however, in practice it is rather unreliable.