ILP Part 92 — Crossing

This is the ninetieth second 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’re going to solve Wykreślanka. We have integers from 1 to 2016. We want to remove as many of them as possible so that any remaining number is not a multiplication of two other remaining numbers. We want to remove as few as possible.

The tricky part here is actually how to generate the model quickly. We could go with something simple like:

So we generate a flag for each number whether it was removed or not. Next, for all possible triplets we encode the requirement that if numbers are not crossed then their multiplication result is not equal to the highest of them. That’s cubic and will take way too long to generate (not to mention the solving time and the memory consumption).

We can make it a little easier by comparing in model-generation time whether (i+1) \times (j+1) is equal to k+1. However, that’s still cubic.

But we can get rid of the third loop and only examine pairs. For each of them we calculate the third number, check if it’s not greater than 2016, and only then include it in the model:

Output:

This was interesting because we calculated quite a lot in the model-generation time. Always do that when possible.