This is the eightieth 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 S and P. The idea is: we start with two non-negative integers and . We calculate and . Now we take digits of and and want all of them to be distinct and form a continuous sequence after sorting. For instance, for and we get and so digits are which are distinct and form a proper sequence.

We want to find a solution for some indicating how long the sequence should be.

Solution:

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 |
int n = 8; int sumDigitsCount = n / 2; int multiplicationDigitsCount = (n + 1) / 2; IVariable x = solver.CreateAnonymous(Domain.PositiveOrZeroInteger); IVariable y = solver.CreateAnonymous(Domain.PositiveOrZeroInteger); IVariable s = solver.Operation<Addition>(x, y); IVariable p = solver.Operation<Multiplication>(x, y); IVariable[] sumDigits = solver.CompositeOperation<Decomposition>(new DecompositionParameters { Base = 10 }, s).ToArray(); for(int i = sumDigitsCount; i < sumDigits.Length; ++i) { solver.Set<Equal>(sumDigits[i], solver.FromConstant(0)); } solver.Set<GreaterOrEqual>(sumDigits[sumDigitsCount - 1], solver.FromConstant(1)); IVariable[] multiplicationDigits = solver.CompositeOperation<Decomposition>(new DecompositionParameters { Base = 10 }, p).ToArray(); for (int i = multiplicationDigitsCount; i < multiplicationDigits.Length; ++i) { solver.Set<Equal>(multiplicationDigits[i], solver.FromConstant(0)); } solver.Set<GreaterOrEqual>(multiplicationDigits[multiplicationDigitsCount - 1], solver.FromConstant(1)); IVariable[] allDigits = sumDigits.Take(sumDigitsCount).Concat(multiplicationDigits.Take(multiplicationDigitsCount)).ToArray(); solver.Set<AllDifferent>(allDigits[0], allDigits.Skip(1).ToArray()); IVariable min = solver.Operation<Minimum>(allDigits); IVariable max = solver.Operation<Maximum>(allDigits); solver.Set<Equal>(solver.Operation<Subtraction>(max, min), solver.FromConstant(n - 1)); solver.Solve(); Console.WriteLine(solver.GetValue(x)); Console.WriteLine(solver.GetValue(y)); |

We start with definition of in line 1.

Next, we calculate how many digits there are in the sum and in result of multiplication. We assume the latter is bigger than the former.

Next, we define initial variables (lines 6-7) and calculations (9-10).

Next, we extract digits in base 10. We make sure that the result of decomposition is not too big (lines 17-20 and 29-32). We basically zero-out too big digits.

Next, we make sure that the decomposition is not too low. So the most significant digit must be non-zero (lines 21 and 33).

Finally, we take all digits and make sure they are distinct (line 39). Next, we calculate min and max (41-42) and then make sure that they differ by . Since all digits are distinct, we get the required effect.

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 49 50 51 52 53 54 55 56 57 58 59 |
Tried aggregator 2 times. MIP Presolve eliminated 199 rows and 56 columns. MIP Presolve modified 631 coefficients. Aggregator did 138 substitutions. Reduced MIP has 539 rows, 291 columns, and 1680 nonzeros. Reduced MIP has 224 binaries, 67 generals, 0 SOSs, and 0 indicators. Presolve time = 0.16 sec. (2.96 ticks) Probing fixed 52 vars, tightened 54 bounds. Probing changed sense of 29 constraints. Probing time = 0.02 sec. (2.19 ticks) Cover probing fixed 0 vars, tightened 12 bounds. Tried aggregator 2 times. MIP Presolve eliminated 116 rows and 64 columns. MIP Presolve modified 101 coefficients. Aggregator did 69 substitutions. Reduced MIP has 354 rows, 158 columns, and 1102 nonzeros. Reduced MIP has 91 binaries, 67 generals, 0 SOSs, and 0 indicators. Presolve time = 0.00 sec. (1.91 ticks) Probing fixed 0 vars, tightened 13 bounds. Probing time = 0.00 sec. (0.39 ticks) Tried aggregator 1 time. MIP Presolve modified 24 coefficients. Reduced MIP has 354 rows, 158 columns, and 1102 nonzeros. Reduced MIP has 91 binaries, 67 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (0.54 ticks) Probing time = 0.00 sec. (0.39 ticks) Clique table members: 26. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: none, using 1 thread. Root relaxation solution time = 0.00 sec. (1.11 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 73 0.0000 103 0 0 0.0000 52 Cuts: 15 111 0 0 0.0000 61 Cuts: 20 158 0 0 0.0000 68 Cuts: 29 200 0 2 0.0000 68 0.0000 200 Elapsed time = 0.36 sec. (45.03 ticks, tree = 0.00 MB, solutions = 0) 1764 75 0.0000 30 0.0000 9658 * 2115 0 integral 0 0.0000 0.0000 13726 0.00% Implied bound cuts applied: 33 Flow cuts applied: 1 Mixed integer rounding cuts applied: 6 Zero-half cuts applied: 12 Lift and project cuts applied: 1 Gomory fractional cuts applied: 6 Root node processing (before b&c): Real time = 0.36 sec. (45.02 ticks) Sequential b&c: Real time = 0.80 sec. (333.65 ticks) ------------ Total (root+branch&cut) = 1.16 sec. (378.67 ticks) 3923 2 |