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 function in ILP. Last time we used comparisons, today we will perform bit operations.
Having non-negative variables and we want to calculate . First, we decompose variables into its binary representation as in multiplication. Nest, we use the following trick: if then there must be a n index for which is one and is zero.
Proof: let’s assume that which means that , and there is no index for which and . At the same time . But since there is no index we want to find, each is not greater than zero. So the whole sum is not greater than zero — contradiction.
Now we only need to find this index.
We will simply bruteforce index. For each position we define the following variables:
Now, is desired index if and only if is one and all for is zero:
The only missing bit:
Now we can perform multiplication to select maximum value using calculated flag.