This is the sixtieth ninth 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’ll solve Krypto 3 po 3 riddles. With ILP and proper library they can be very readable.
We start with the following:
|
1 2 3 4 5 6 |
var letters = Enumerable.Range(0, 'I' - 'A' + 1).Select(l => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray(); foreach(var letter in letters){ letter.Set<LessOrEqual>(solver.FromConstant(9)); } solver.Set<AllDifferent>(letters[0], letters.Skip(1).ToArray()); |
So we define 9 variables for letters A to I. We make sure their values are different.
Now, riddle 1:
|
1 2 3 4 5 6 |
letters[0].Operation<Addition>(letters[1]).Operation<Multiplication>(letters[2]).Set<Equal>(solver.FromConstant(27)); letters[3].Operation<Multiplication>(letters[4]).Operation<Addition>(letters[5]).Set<Equal>(solver.FromConstant(22)); letters[6].Operation<Division>(letters[7]).Operation<Addition>(letters[8]).Set<Equal>(solver.FromConstant(15)); letters[0].Operation<Multiplication>(letters[3]).Operation<Subtraction>(letters[6]).Set<Equal>(solver.FromConstant(26)); letters[1].Operation<Division>(letters[4]).Operation<Addition>(letters[7]).Set<Equal>(solver.FromConstant(3)); letters[2].Operation<Multiplication>(letters[5]).Operation<Subtraction>(letters[8]).Set<Equal>(solver.FromConstant(18)); |
|
1 2 3 4 5 6 7 8 9 10 |
Total (root+branch&cut) = 0.03 sec. (24.77 ticks) A - 5 B - 4 C - 3 D - 7 E - 2 F - 8 G - 9 H - 1 I - 6 |
So it took CPLEX 30 milliseconds to find solution. We can also see that we can just read formulas like sentences. Obviously, if we had operator overloading in place then it would be even easier to write. Microsoft Solver Foundation gives you this nice experience.
Riddle 2:
|
1 2 3 4 5 6 |
letters[0].Operation<Addition>(letters[1]).Operation<Subtraction>(letters[2]).Set<Equal>(solver.FromConstant(1)); letters[3].Operation<Multiplication>(letters[4]).Operation<Division>(letters[5]).Set<Equal>(solver.FromConstant(1)); letters[6].Operation<Subtraction>(letters[7]).Operation<Subtraction>(letters[8]).Set<Equal>(solver.FromConstant(1)); letters[0].Operation<Multiplication>(letters[3]).Operation<Subtraction>(letters[6]).Set<Equal>(solver.FromConstant(1)); letters[1].Operation<Addition>(letters[4]).Operation<Division>(letters[7]).Set<Equal>(solver.FromConstant(1)); letters[2].Operation<Subtraction>(letters[5]).Operation<Subtraction>(letters[8]).Set<Equal>(solver.FromConstant(1)); |
|
1 2 3 4 5 6 7 8 9 10 |
Total (root+branch&cut) = 0.11 sec. (32.89 ticks) A - 5 B - 4 C - 8 D - 2 E - 3 F - 6 G - 9 H - 7 I - 1 |
And riddle 3:
|
1 2 3 4 5 6 |
letters[0].Operation<Subtraction>(letters[1]).Operation<RealDivision>(letters[2]).Set<Equal>(letters[2]); letters[3].Operation<RealDivision>(letters[4]).Operation<Addition>(letters[5]).Set<Equal>(letters[3]); letters[6].Operation<RealDivision>(letters[7]).Operation<Addition>(letters[8]).Set<Equal>(letters[1]); letters[0].Operation<Multiplication>(letters[3]).Operation<Subtraction>(letters[6]).Set<Equal>(letters[5].Operation<Multiplication>(solver.FromConstant(10)).Operation<Addition>(letters[0])); letters[1].Operation<Multiplication>(letters[4]).Operation<Multiplication>(letters[7]).Set<Equal>(letters[6].Operation<Multiplication>(solver.FromConstant(10)).Operation<Addition>(letters[7])); letters[2].Operation<Addition>(letters[5]).Operation<Multiplication>(letters[8]).Set<Equal>(letters[4].Operation<Multiplication>(solver.FromConstant(10)).Operation<Addition>(letters[8])); |
|
1 2 3 4 5 6 7 8 9 10 |
Total (root+branch&cut) = 0.17 sec. (114.89 ticks) A - 8 B - 7 C - 1 D - 9 E - 3 F - 6 G - 4 H - 2 I - 5 |
Riddle 3 solved with SCIP:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
SCIP Status : problem is solved [optimal solution found] Solving Time (sec) : 20.50 Solving Nodes : 32 Primal Bound : +0.00000000000000e+000 (1 solutions) Dual Bound : +0.00000000000000e+000 Gap : 0.00 % A - 8 B - 7 C - 1 D - 9 E - 3 F - 6 G - 4 H - 2 I - 5 |
You can see that it took over 20 seconds (I’m using old SCIP, though).
Riddle 3 with Mipcl:
|
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
Start preprocessing: Rows - 18356, Cols - 18356 (Int - 11008, Bin - 3691), NZs - 37486 ==================================== Probing ===================================== Time Round Probed vars Fixed vars Mod. entries New var bds Implications 0.163 1 620 328 1195 466 698 0.181 2 292 59 302 817 414 0.198 3 243 1 19 234 159 0.216 4 242 0 23 217 154 ================================================================================== Searching for symmetries... 0 symmetry generators found After preprocessing: Rows - 736, Cols - 368 (Int - 242, Bin - 181), NZs - 1981 Scaling... Min exp = -9, Max exp = 10 Preprocessing Time: 0.251 Optimizing... Building initial basis... Time Its Deg. Its Method Obj 0.256 100 99 D/S 0.0000 0.270 200 199 D/S 0.0000 0.278 207 206 D/S 0.0000 Generating cuts... Time Obj Frac vars Cuts 0.289 0.0000 129 181 0.321 0.0000 131 60 0.341 0.0000 135 65 0.353 0.0000 129 28 Restarting ... Start preprocessing: Rows - 776, Cols - 368 (Int - 242, Bin - 181), NZs - 2174 ==================================== Probing ===================================== Time Round Probed vars Fixed vars Mod. entries New var bds Implications 0.633 1 242 0 11 222 154 ================================================================================== After preprocessing: Rows - 763, Cols - 368 (Int - 242, Bin - 181), NZs - 2121 Scaling... Min exp = -9, Max exp = 10 Building initial basis... Time Its Deg. Its Method Obj 0.671 100 99 D/S 0.0000 0.697 200 199 D/S 0.0000 0.711 290 265 D/S 0.0000 0.716 1 0 P/S 0.0000 Generating cuts... Time Obj Frac vars Cuts 0.737 0.0000 121 88 0.809 0.0000 138 52 0.829 0.0000 163 103 0.853 0.0000 142 60 0.878 0.0000 117 17 0.913 0.0000 116 61 Cut statistics ========== Cuts = Generated === Used click 11 5 knapsack 3 0 mixed knapsack 32 7 mir 296 65 sparse MOD2 137 45 sparse Gomory 10 2 parity 11 3 var bound 85 11 disjunction 45 3 ========= total 630 141 After processing root node: Rows - 792, Cols - 368 (Int - 242, Bin - 181), NZs - 2256 Time Nodes Leaves Sols Best Solution Upper Bound Gap% 1.321 1 1 0 -inf 0.0000 inf 2.475 85 0 1 0.0000 0.0000 0.00 =========================================== MIPCL version 2.5.4 Solution time: 3.496 Branch-and-Cut nodes: 85 Objective value: 0.0000 - optimality proven A - 8 B - 7 C - 1 D - 9 E - 3 F - 6 G - 4 H - 2 I - 5 |
You can see Mipcl finished in 3.5 second.
I also tried GLPK, MSF, lp_solve, and CBC (via OrTools) – none of them could solve the problem is reasonable (< 1 minute) time.