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*}

Now, i is desired index if and only if c_i is one and all c_{j} for j > i is zero:

    \[ d_i = c_i \wedge \neg c_{i+1} \wedge \neg c_{i+2} \wedge \neg c_{i+3} \wedge \cdots \]

The only missing bit:

    \[ a_{isGreater} = d_0 \vee d_1 \vee d_2 \vee d_3 \vee \cdots \]

Now we can perform multiplication to select maximum value using calculated flag.