This is the forty thrid 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 implement $\max$ function in ILP. Last time we used comparisons, today we will perform bit operations.

Idea

Having non-negative variables $a$ and $b$ we want to calculate $c = \max(a,b)$ . First, we decompose variables into its binary representation as in multiplication. Nest, we use the following trick: if $a > b$ then there must be a n index $i$ for which $a_i$ is one and $b_i$ is zero.

Proof: let’s assume that $a > b$ which means that $a - b > 0$ , and there is no index for which $a_i = 1$ and $b_i = 0$ . At the same time $a - b = \sum a_i 2^i - b_i 2^i = \sum (a_i - b_i)2^i$ . But since there is no index we want to find, each $a_i - b_i$ is not greater than zero. So the whole sum is not greater than zero — contradiction.

Now we only need to find this index.

Finding index

We will simply bruteforce index. For each position we define the following variables:

$\begin{gather*} a_{isOne, i} = a_i \stackrel{?}{=} 1 \\ b_{isZero, i} = b_i \stackrel{?}{=} 0 \\ c_{i} = a_{isOne, i} \wedge b_{isZero, i} \end{gather*}$