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 for which we know that a sum of an arithmetic progression is equal to (concatenated , , and ). Let’s solve it with ILP.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
var x = solver.CreateAnonymous(Domain.PositiveOrZeroInteger); var sum = x.Operation<Multiplication>(x.Operation<Addition>(solver.FromConstant(1))).Operation<Division>(solver.FromConstant(2)); var extendedX = x.Operation<Multiplication>(solver.FromConstant(1000)).Operation<Addition>(solver.FromConstant(153)); List<IVariable> conjunctions = new List<IVariable>(); for (int t = 1; t <= 1e7; t *= 10) { var c = solver.FromConstant(t).Operation<IsLessOrEqual>(extendedX) .Operation<Conjunction>(solver.FromConstant(t * 10).Operation<IsGreaterOrEqual>(extendedX)); conjunctions.Add(c); c.Operation<MaterialImplication>(solver.FromConstant(t * 10).Operation<Addition>(extendedX).Operation<IsEqual>(sum)) .Set<Equal>(solver.FromConstant(1)); } solver.Operation<Addition>(conjunctions.ToArray()).Set<Equal>(solver.FromConstant(1)); solver.AddGoal("goal", solver.FromConstant(0)); solver.Solve(); Console.WriteLine(solver.GetValue(x)); |

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 and . Finally, we generate consecutive powers of ten and use the one greater than the . We use material implication to perform the “if” condition.

CPLEX output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
Tried aggregator 2 times. MIP Presolve eliminated 146 rows and 45 columns. MIP Presolve modified 666 coefficients. Aggregator did 172 substitutions. Reduced MIP has 474 rows, 268 columns, and 1438 nonzeros. Reduced MIP has 203 binaries, 65 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (3.98 ticks) Probing fixed 125 vars, tightened 443 bounds. Probing changed sense of 15 constraints. Probing time = 0.02 sec. (3.23 ticks) Cover probing fixed 0 vars, tightened 206 bounds. Tried aggregator 3 times. MIP Presolve eliminated 321 rows and 196 columns. MIP Presolve modified 209 coefficients. Aggregator did 29 substitutions. Reduced MIP has 124 rows, 43 columns, and 365 nonzeros. Reduced MIP has 13 binaries, 30 generals, 0 SOSs, and 0 indicators. Presolve time = 0.00 sec. (1.37 ticks) Probing time = 0.00 sec. (0.14 ticks) Tried aggregator 2 times. Aggregator did 1 substitutions. Reduced MIP has 123 rows, 42 columns, and 363 nonzeros. Reduced MIP has 13 binaries, 29 generals, 0 SOSs, and 0 indicators. Presolve time = 0.00 sec. (0.38 ticks) Probing time = 0.00 sec. (0.13 ticks) Clique table members: 1. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: none, using 1 thread. Root relaxation solution time = 0.00 sec. (0.54 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 18 0.0000 52 0 0 0.0000 18 MIRcuts: 2 67 0 2 0.0000 18 0.0000 67 Elapsed time = 0.06 sec. (18.10 ticks, tree = 0.00 MB, solutions = 0) Mixed integer rounding cuts applied: 1 Root node processing (before b&c): Real time = 0.06 sec. (18.09 ticks) Sequential b&c: Real time = 0.00 sec. (0.55 ticks) ------------ Total (root+branch&cut) = 0.06 sec. (18.63 ticks) ILOG.CPLEX.CpxException: CPLEX Error 1217: No solution exists. |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Start preprocessing: Rows - 3345, Cols - 3345 (Int - 2424, Bin - 716), NZs - 6788 ==================================== Probing ===================================== Time Round Probed vars Fixed vars Mod. entries New var bds Implications 0.120 1 303 89 487 1042 444 0.170 2 214 38 284 363 246 0.177 3 176 80 254 514 339 0.195 4 96 26 184 276 42 0.202 5 70 14 166 176 5 0.204 6 56 56 333 153 13 ================================================================================== After preprocessing: Rows - 0, Cols - 0 (Int - 0, Bin - 0), NZs - 0 Preprocessing Time: 0.204 =========================================== MIPCL version 2.5.4 Solution time: 0.204 Branch-and-Cut nodes: 1 5582 Objective value: 0.0000 - optimality proven |

MIPCL succeeded.