ILP Part 83 — Concatenation

This is the eightieth third 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 solve Dolepki. We have some natural number n for which we know that a sum of an arithmetic progression 1+2+\ldots+n is equal to 1x153 (concatenated 1, x, and 153). Let’s solve it with ILP.

Should be pretty straightforward. First, we calculate the sum of progression by using well known formula. Next, we calculate extendedX which is a helper variable with concatenated x and 153. Finally, we generate consecutive powers of ten and use the one greater than the x. We use material implication to perform the “if” condition.

CPLEX output:

That’s remarkable. It’s one of the problems where CPLEX fails to find a solution even though it’s there. However, we can try MIPCL:

MIPCL succeeded.