ILP Part 71 — Typo – Random IT Utensils

This is the seventieth first part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Let’s solve the Literówka problem. It’s almost a regular riddle with digits hidden behind letters but this time one letter in the final sum is incorrect. How do we represent this in ILP?

Let’s see the code first:

var variables = Enumerable.Range(0, 6).Select(i => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray();

foreach(var v in variables){
v.Set<LessOrEqual>(solver.FromConstant(9));
}
solver.Set<AllDifferent>(variables[0], variables.Skip(1).ToArray());

var ten = solver.FromConstant(10);

var s1 = variables[3].Operation<Multiplication>(variables[1]);
var sr1 = s1.Operation<Remainder>(ten);
var sd1 = s1.Operation<Division>(ten);
sr1.Set<Equal>(variables[5]);

var s2 = variables[3].Operation<Multiplication>(variables[0]).Operation<Addition>(sd1);
var sr2 = s2.Operation<Remainder>(ten);
var sd2 = s2.Operation<Division>(ten);
sr2.Set<Equal>(variables[5]);

var s3 = sd2;
var sr3 = s3;
s3.Set<Equal>(variables[5]);

var s4 = variables[2].Operation<Multiplication>(variables[1]);
var sr4 = s4.Operation<Remainder>(ten);
var sd4 = s4.Operation<Division>(ten);
sr4.Set<Equal>(variables[0]);

var s5 = variables[2].Operation<Multiplication>(variables[0]).Operation<Addition>(sd4);
var sr5 = s5.Operation<Remainder>(ten);
var sd5 = s5.Operation<Division>(ten);
sr5.Set<Equal>(variables[0]);

var s6 = sd5;
var sr6 = s6;
s6.Set<Equal>(variables[0]);


var rr1 = sr1;

var r2 = sr2.Operation<Addition>(sr4);
var rr2 = r2.Operation<Remainder>(ten);
var rd2 = r2.Operation<Division>(ten);

var r3 = sr3.Operation<Addition>(sr5).Operation<Addition>(rd2);
var rr3 = r3.Operation<Remainder>(ten);
var rd3 = r3.Operation<Division>(ten);

var r4 = sr6.Operation<Addition>(rd3);
var rr4 = r4;
r4.Set<LessOrEqual>(solver.FromConstant(9));

var isCorrect = Enumerable.Range(0, 4).Select(i => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();
solver.Operation<Addition>(isCorrect).Set<Equal>(solver.FromConstant(3));

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(isCorrect[0], solver.Operation<IsEqual>(rr1, variables[5])));
solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(isCorrect[1], solver.Operation<IsEqual>(rr2, variables[4])));
solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(isCorrect[2], solver.Operation<IsEqual>(rr3, variables[4])));
solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(isCorrect[3], solver.Operation<IsEqual>(rr4, variables[5])));

var variables = Enumerable.Range(0, 6).Select(i => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray();

foreach(var v in variables){

v.Set<LessOrEqual>(solver.FromConstant(9));

}

solver.Set<AllDifferent>(variables[0], variables.Skip(1).ToArray());

var ten = solver.FromConstant(10);

var s1 = variables[3].Operation<Multiplication>(variables[1]);

var sr1 = s1.Operation<Remainder>(ten);

var sd1 = s1.Operation<Division>(ten);

sr1.Set<Equal>(variables[5]);

var s2 = variables[3].Operation<Multiplication>(variables[0]).Operation<Addition>(sd1);

var sr2 = s2.Operation<Remainder>(ten);

var sd2 = s2.Operation<Division>(ten);

sr2.Set<Equal>(variables[5]);

var s3 = sd2;

var sr3 = s3;

s3.Set<Equal>(variables[5]);

var s4 = variables[2].Operation<Multiplication>(variables[1]);

var sr4 = s4.Operation<Remainder>(ten);

var sd4 = s4.Operation<Division>(ten);

sr4.Set<Equal>(variables[0]);

var s5 = variables[2].Operation<Multiplication>(variables[0]).Operation<Addition>(sd4);

var sr5 = s5.Operation<Remainder>(ten);

var sd5 = s5.Operation<Division>(ten);

sr5.Set<Equal>(variables[0]);

var s6 = sd5;

var sr6 = s6;

s6.Set<Equal>(variables[0]);

var rr1 = sr1;

var r2 = sr2.Operation<Addition>(sr4);

var rr2 = r2.Operation<Remainder>(ten);

var rd2 = r2.Operation<Division>(ten);

var r3 = sr3.Operation<Addition>(sr5).Operation<Addition>(rd2);

var rr3 = r3.Operation<Remainder>(ten);

var rd3 = r3.Operation<Division>(ten);

var r4 = sr6.Operation<Addition>(rd3);

var rr4 = r4;

r4.Set<LessOrEqual>(solver.FromConstant(9));

var isCorrect = Enumerable.Range(0, 4).Select(i => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();

solver.Operation<Addition>(isCorrect).Set<Equal>(solver.FromConstant(3));

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(isCorrect[0], solver.Operation<IsEqual>(rr1, variables[5])));

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(isCorrect[1], solver.Operation<IsEqual>(rr2, variables[4])));

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(isCorrect[2], solver.Operation<IsEqual>(rr3, variables[4])));

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(isCorrect[3], solver.Operation<IsEqual>(rr4, variables[5])));

We start with lines 1-6 in which we define variables for letters as if they were all correct. We make them all different and set ranges. variable[0] stands for letter A.

In line 8 we add helper variable as we’ll use this constant many times.

Next, in lines 10-36 we implement long addition. Letter “s” stands for sum, “r” for remainder, “d” for integer division. We just unroll the addition algorithm and make it explicit.

Next, in lines 39-51 we implement addition for the final result. Again, first “r” stands for result, second “r” for remainder, “d” for division. No magic here.

Finally, we need to implement the constraint that exactly one letter in final sum is a typo. So we create binary variables in line 53 and make sure three of them are set (line 54).

Finally, we add constraints based on material implication. If given digit is correct then it must meet some constraint. So we go through digits one by one and if they are correct then they must be equal to some other well known variable.

Output:

Tried aggregator 3 times.
MIP Presolve eliminated 545 rows and 181 columns.
MIP Presolve modified 955 coefficients.
Aggregator did 354 substitutions.
Reduced MIP has 862 rows, 513 columns, and 2597 nonzeros.
Reduced MIP has 419 binaries, 94 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (8.59 ticks)
Probing fixed 266 vars, tightened 156 bounds.
Probing changed sense of 27 constraints.
Probing time = 0.00 sec. (2.42 ticks)
Cover probing fixed 0 vars, tightened 248 bounds.
Tried aggregator 2 times.
MIP Presolve eliminated 577 rows and 371 columns.
MIP Presolve modified 155 coefficients.
Aggregator did 59 substitutions.
Reduced MIP has 226 rows, 83 columns, and 667 nonzeros.
Reduced MIP has 37 binaries, 46 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (1.53 ticks)
Probing time = 0.00 sec. (0.26 ticks)
Tried aggregator 1 time.
Reduced MIP has 226 rows, 83 columns, and 667 nonzeros.
Reduced MIP has 37 binaries, 46 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.36 ticks)
Probing time = 0.00 sec. (0.32 ticks)
Clique table members: 60.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (0.41 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000     7                      0.0000       17
      0     0        0.0000    52                    Cuts: 24      111
      0     0        0.0000    38                    Cuts: 20      164
      0     0        0.0000    22                    Cuts: 23      183
      0     0        0.0000    34                     Cuts: 8      196
*     0+    0                            0.0000        0.0000      196    0.00%
      0     0        cutoff              0.0000        0.0000      196    0.00%
Elapsed time = 0.05 sec. (31.98 ticks, tree = 0.00 MB, solutions = 1)

Clique cuts applied:  3
Cover cuts applied:  1
Implied bound cuts applied:  3
Mixed integer rounding cuts applied:  6
Zero-half cuts applied:  3

Root node processing (before b&c):
  Real time             =    0.08 sec. (32.02 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.08 sec. (32.02 ticks)
3
7
9
6
5
2

Tried aggregator 3 times.

MIP Presolve eliminated 545 rows and 181 columns.

MIP Presolve modified 955 coefficients.

Aggregator did 354 substitutions.

Reduced MIP has 862 rows, 513 columns, and 2597 nonzeros.

Reduced MIP has 419 binaries, 94 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (8.59 ticks)

Probing fixed 266 vars, tightened 156 bounds.

Probing changed sense of 27 constraints.

Probing time = 0.00 sec. (2.42 ticks)

Cover probing fixed 0 vars, tightened 248 bounds.

Tried aggregator 2 times.

MIP Presolve eliminated 577 rows and 371 columns.

MIP Presolve modified 155 coefficients.

Aggregator did 59 substitutions.

Reduced MIP has 226 rows, 83 columns, and 667 nonzeros.

Reduced MIP has 37 binaries, 46 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (1.53 ticks)

Probing time = 0.00 sec. (0.26 ticks)

Tried aggregator 1 time.

Reduced MIP has 226 rows, 83 columns, and 667 nonzeros.

Reduced MIP has 37 binaries, 46 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (0.36 ticks)

Probing time = 0.00 sec. (0.32 ticks)

Clique table members: 60.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.00 sec. (0.41 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 7 0.0000 17

0 0 0.0000 52 Cuts: 24 111

0 0 0.0000 38 Cuts: 20 164

0 0 0.0000 22 Cuts: 23 183

0 0 0.0000 34 Cuts: 8 196

* 0+ 0 0.0000 0.0000 196 0.00%

0 0 cutoff 0.0000 0.0000 196 0.00%

Elapsed time = 0.05 sec. (31.98 ticks, tree = 0.00 MB, solutions = 1)

Clique cuts applied: 3

Cover cuts applied: 1

Implied bound cuts applied: 3

Mixed integer rounding cuts applied: 6

Zero-half cuts applied: 3

Root node processing (before b&c):

Real time = 0.08 sec. (32.02 ticks)

Parallel b&c, 8 threads:

Real time = 0.00 sec. (0.00 ticks)

Sync time (average) = 0.00 sec.

Wait time (average) = 0.00 sec.

------------

Total (root+branch&cut) = 0.08 sec. (32.02 ticks)

So the final riddle looks like this:

    37
X   96
------
   222
+ 333
------
  3552

X 96

------

222

+ 333

------

3552

So we can see that the leftmost digit was a typo.