This is the one hundredth 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 Literowce. It’s similar to ILP Part 47 — Battleship puzzle. We have a board and some ships with letters on them. We need to put ships on the board, so they don’t collide with each other. The board has numbers on top and on the left. These numbers indicate how many ship parts are in given column or row. Also, the board has letters on the right and at the bottom. These letters indicate what is the letter closes to the edge in given row or column.

First, let’s start with the code:

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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 |
var ships = new []{ "123", "21", "32", "1", "2", "3" }; var columnNumbers = new []{1, 1, 3, 1, 2, 1, 1}; var rowNumbers = new []{2, 2, 1, 1, 2, 0, 2}; var columnLetters = new []{2, 3, 3, 1, 2, 1, 2}; var rowLetters = new []{2, 3, 3, 1, 3, 0, 2}; var width = columnNumbers.Length; var height = rowNumbers.Length; var shipsCount = ships.Length; // Right, down, left, up var directions = 4; var assignedShips = Enumerable.Range(0, height).Select(h => Enumerable.Range(0, width).Select(w => Enumerable.Range(0, shipsCount).Select(s => Enumerable.Range(0, directions).Select(d => solver.CreateAnonymous(Domain.BinaryInteger) ).ToArray() ).ToArray() ).ToArray() ).ToArray(); var boardNumbers = Enumerable.Range(0, height).Select(h => Enumerable.Range(0, width).Select(w => solver.CreateAnonymous(Domain.PositiveOrZeroInteger) ).ToArray() ).ToArray(); // Make sure each field has at most one ship head for(int h = 0; h < height; ++h){ for(int w = 0; w < width; ++ w){ solver.Set<LessOrEqual>( solver.Operation<Addition>( Enumerable.Range(0, shipsCount).SelectMany(s => Enumerable.Range(0, directions).Select(d => assignedShips[h][w][s][d] ) ).ToArray() ), solver.FromConstant(1) ); } } // Make sure each ship has its head somewhere for(int s = 0; s < shipsCount;++s){ solver.Set<Equal>( solver.Operation<Addition>( Enumerable.Range(0, height).SelectMany(h => Enumerable.Range(0, width).SelectMany(w => Enumerable.Range(0, directions).Select(d => assignedShips[h][w][s][d] ) ) ).ToArray() ), solver.FromConstant(1) ); } // Propagate numbers from heads for(int h = 0; h < height; ++h){ for(int w = 0; w < width; ++ w){ for(int s = 0; s < shipsCount;++s){ for(int d = 0; d < directions; ++ d){ for(int p = 0; p < ships[s].Length; ++p){ int finalH = h; int finalW = w; if(d == 0 && w + p < width){ finalW = w + p; }else if(d == 1 && h + p < height){ finalH = h + p; }else if(d == 2 && w - p >= 0){ finalW = w - p; }else if(d == 3 && h - p >= 0){ finalH = h - p; } solver.Set<Equal>( solver.FromConstant(1), solver.Operation<MaterialImplication>( assignedShips[h][w][s][d].Operation<IsEqual>(solver.FromConstant(1)), boardNumbers[finalH][finalW].Operation<IsEqual>(solver.FromConstant(int.Parse(ships[s][p] + ""))) ) ); } } } } } // Make sure that there is as many numbers as ship parts solver.Set<Equal>( solver.Operation<Addition>( Enumerable.Range(0, height).SelectMany(h => Enumerable.Range(0, width).Select(w => boardNumbers[h][w].Operation<IsGreaterOrEqual>(solver.FromConstant(1)) ) ).ToArray() ), solver.FromConstant(ships.Select(s => s.Length).Sum()) ); // Make sure ships do not run out of the board for(int h = 0; h < height; ++h){ for(int w = 0; w < width; ++ w){ for(int s = 0; s < shipsCount;++s){ for(int d = 0; d < directions; ++ d){ var shipLength = ships[s].Length; if( (d == 0 && w + shipLength - 1 >= width) || (d == 1 && h + shipLength - 1 >= height) || (d == 2 && w - shipLength + 1 < 0) || (d == 3 && h - shipLength + 1 < 0) ){ assignedShips[h][w][s][d].Set<Equal>(solver.FromConstant(0)); } } } } } // Make sure ships do not collide for(int h = 0; h < height; ++h){ for(int w = 0; w < width; ++ w){ for(int s = 0; s < shipsCount;++s){ for(int d = 0; d < directions; ++ d){ var shipLength = ships[s].Length; var startH = d == 3 ? h - shipLength : h - 1; var hLength = d == 1 || d == 3 ? shipLength + 2: 3; var startW = d == 2 ? w - shipLength : w - 1; var wLength = d == 0 || d == 2 ? shipLength + 2 : 3; var allNeighbouringFields = Enumerable.Range(startH, hLength).Where(h2 => h2 >= 0 && h2 < height).SelectMany(h2 => Enumerable.Range(startW, wLength).Where(w2 => w2 >= 0 && w2 < width).Where(w2 => { return d == 0 ? !(h2 == h && w2 >= w && w2 < w + shipLength) : d == 1 ? !(w2 == w && h2 >= h && h2 < h + shipLength) : d == 2 ? !(h2 == h && w2 > w - shipLength && w2 <= w) : !(w2 == w && h2 >= h - shipLength && h2 <= h); }).Select(w2 => boardNumbers[h2][w2] ) ).ToArray(); var neighboursSum = solver.Operation<Addition>(allNeighbouringFields); solver.Set<Equal>( solver.FromConstant(1), solver.Operation<MaterialImplication>( assignedShips[h][w][s][d].Operation<IsEqual>(solver.FromConstant(1)), neighboursSum.Operation<IsEqual>(solver.FromConstant(0)) ) ); } } } } // Make sure there is no other ship head on a ship for(int h = 0; h < height; ++h){ for(int w = 0; w < width; ++ w){ for(int s = 0; s < shipsCount;++s){ for(int d = 0; d < directions; ++ d){ var shipLength = ships[s].Length; var startH = d == 3 ? h - shipLength + 1 : h; var hLength = d == 1 || d == 3 ? shipLength : 1; var startW = d == 2 ? w - shipLength + 1: w; var wLength = d == 0 || d == 2 ? shipLength : 1; var allNeighbouringFields = Enumerable.Range(startH, hLength).Where(h2 => h2 >= 0 && h2 < height).SelectMany(h2 => Enumerable.Range(startW, wLength).Where(w2 => w2 >= 0 && w2 < width).Where(w2 => !(h2 == h && w2 == w)).SelectMany(w2 => Enumerable.Range(0, shipsCount).SelectMany(s2 => Enumerable.Range(0, directions).Select(d2 => assignedShips[h2][w2][s2][d2] ) ) ) ).ToArray(); if(allNeighbouringFields.Length == 0){ continue; } var neighboursSum = solver.Operation<Addition>(allNeighbouringFields); solver.Set<Equal>( solver.FromConstant(1), solver.Operation<MaterialImplication>( assignedShips[h][w][s][d].Operation<IsEqual>(solver.FromConstant(1)), neighboursSum.Operation<IsEqual>(solver.FromConstant(0)) ) ); } } } } // Make sure we put correct number of pieces in each row for(int h = 0; h < height; ++h){ solver.Set<Equal>( solver.Operation<Addition>( Enumerable.Range(0, width).Select(w => boardNumbers[h][w].Operation<IsGreaterOrEqual>(solver.FromConstant(1))).ToArray() ), solver.FromConstant(rowNumbers[h]) ); } // Make sure we put correct number of pieces in each column for(int w = 0; w < width; ++w){ solver.Set<Equal>( solver.Operation<Addition>( Enumerable.Range(0, height).Select(h => boardNumbers[h][w].Operation<IsGreaterOrEqual>(solver.FromConstant(1))).ToArray() ), solver.FromConstant(columnNumbers[w]) ); } // Make sure very right numbers match for(int h = 0; h < height; ++h){ solver.Set<Equal>( Enumerable.Range(0, width) .Select(w => boardNumbers[h][w]) .Aggregate( solver.FromConstant(0), (a, b) => solver.Operation<Condition>( b.Operation<IsGreaterOrEqual>(solver.FromConstant(1)), b, a ) ), solver.FromConstant(rowLetters[h]) ); } // Make sure very bottom numbers match for(int w = 0; w < width; ++w){ solver.Set<Equal>( Enumerable.Range(0, height) .Select(h => boardNumbers[h][w]) .Aggregate( solver.FromConstant(0), (a, b) => solver.Operation<Condition>( b.Operation<IsGreaterOrEqual>(solver.FromConstant(1)), b, a ) ), solver.FromConstant(columnLetters[w]) ); } var goal = solver.FromConstant(0); solver.Solve(); for(int h = 0; h < height; ++h){ for(int w = 0; w < width; ++ w){ var hasHead = false; for(int s = 0; s < shipsCount;++s){ for(int d = 0; d < directions; ++ d){ if(solver.GetValue(assignedShips[h][w][s][d]) > 0.5){ hasHead = true; Console.Write(s + "_" + d + ","); } } } if(!hasHead){ Console.Write(","); } } Console.WriteLine(); } Console.WriteLine(); for(int h = 0; h < height; ++h){ for(int w = 0; w < width; ++ w){ var n = Math.Round(solver.GetValue(boardNumbers[h][w])); Console.Write(n == 0 ? " " : n.ToString()); } Console.WriteLine(); } Console.WriteLine(); |

That’s long. Let’s go part by part.

First, we need to define our ships. We’re not going to use letters. We’ll go with numbers instead. So the ship ABC is encoded as 123. This is in lines 1-8.

Next, we store numbers indicating how many parts are in given row and column. This is in lines 10-11.

Next, we store numbers indicating which ship part is the closest to the edge. This is in lines 12-13. Again, we replaced letters with numbers.

Next, a couple of helper variables in lines 15-19. Also, we’ll use directions represented as numbers. 0 indicates a ship stored horizontally to the right. 1 is going down. 2 is going left. 3 is going up.

Now, we need to represent our model. First, for each field at the board we’ll store a binary flag indicating whether the first part of the ship in given rotation is stored in this field. We call this part a “ship head”. This is in lines 21-29.

Another model is the actual numbers assigned to each field of the board. These numbers are non-negative, and 0 indicates that a given field is empty. This is in lines 31-35.

Next, we encode some basic rules. Each field can have at most one ship head – lines 37-51. Each ship must have its head somewhere – lines 53-67.

Next, every ship must assign numbers somewhere. So if we take ship 123 (ABC) and put its head in field `3,2`

, then fields `3,2; 3,3; 3,4`

must have numbers assigned. We use an “if” condition encoded in ILP. This is in lines 70-99.

Next, we need to make sure that all fields without ships have no numbers assigned to them. So we count fields with numbers, and then we make sure this is equal to the total number of ship parts we have. This is in lines 101-111.

Next, we need to make sure that we don’t put a ship too close to the edge that would make it fall off the board. This is in lines 113-130.

Next, we need to make sure ships do not collide. We iterate over all fields, ships, and directions. Now, depending on the ship length and its direction, we take the correct rectangle (lines 143-153) without the ship itself. Next, we sum numbers in that rectangle, and set the sum to be equal to zero, so there are no numbers assigned. This is in lines 132-166.

Next, we make sure that when we put a ship on the board then no other ship can be put on top of it. So there is no other ship head on the top of some other ship. This is in lines 168-206.

Finally, we make sure we have correct number of ship parts in each row and column – lines 208-226.

Next, we do the same for very right and very bottom numbers in each row and column. We use condition to take the edge-most number. This is in lines 228-260.

That’s it. The output is:

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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
Tried aggregator 3 times. MIP Presolve eliminated 37023 rows and 18372 columns. MIP Presolve modified 77855 coefficients. Aggregator did 21745 substitutions. Reduced MIP has 22830 rows, 12005 columns, and 84963 nonzeros. Reduced MIP has 11600 binaries, 405 generals, 0 SOSs, and 0 indicators. Presolve time = 0.47 sec. (381.49 ticks) Probing fixed 1264 vars, tightened 377 bounds. Probing time = 1.36 sec. (450.22 ticks) Tried aggregator 2 times. MIP Presolve eliminated 6511 rows and 4392 columns. MIP Presolve modified 686 coefficients. Aggregator did 58 substitutions. Reduced MIP has 16261 rows, 7555 columns, and 57744 nonzeros. Reduced MIP has 7192 binaries, 363 generals, 0 SOSs, and 0 indicators. Presolve time = 0.16 sec. (115.80 ticks) Probing time = 0.08 sec. (14.53 ticks) Tried aggregator 1 time. MIP Presolve modified 10 coefficients. Reduced MIP has 16261 rows, 7555 columns, and 57744 nonzeros. Reduced MIP has 7192 binaries, 363 generals, 0 SOSs, and 0 indicators. Presolve time = 0.06 sec. (33.70 ticks) Probing time = 0.08 sec. (15.39 ticks) Clique table members: 40522. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Root relaxation solution time = 0.30 sec. (404.55 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 2744 0.0000 2546 0 0 0.0000 2152 Cuts: 4165 3126 0 0 0.0000 1993 Cuts: 4165 4510 0 0 0.0000 1816 Cuts: 1461 5047 0 0 0.0000 2140 Cuts: 824 5761 0 0 0.0000 1369 Cuts: 1162 6029 Repeating presolve. Tried aggregator 3 times. MIP Presolve eliminated 5864 rows and 2848 columns. MIP Presolve modified 425 coefficients. Aggregator did 11 substitutions. Reduced MIP has 10388 rows, 4696 columns, and 38727 nonzeros. Reduced MIP has 4381 binaries, 315 generals, 0 SOSs, and 0 indicators. Presolve time = 0.22 sec. (143.80 ticks) Probing fixed 284 vars, tightened 1 bounds. Probing changed sense of 95 constraints. Probing time = 0.28 sec. (95.69 ticks) Tried aggregator 3 times. MIP Presolve eliminated 818 rows and 395 columns. MIP Presolve modified 474 coefficients. Aggregator did 10 substitutions. Reduced MIP has 9558 rows, 4291 columns, and 35068 nonzeros. Reduced MIP has 3988 binaries, 303 generals, 0 SOSs, and 0 indicators. Presolve time = 0.16 sec. (120.56 ticks) Probing time = 0.11 sec. (18.86 ticks) Tried aggregator 1 time. MIP Presolve eliminated 1 rows and 1 columns. MIP Presolve modified 4 coefficients. Reduced MIP has 9557 rows, 4290 columns, and 35065 nonzeros. Reduced MIP has 3987 binaries, 303 generals, 0 SOSs, and 0 indicators. Presolve time = 0.08 sec. (47.62 ticks) Represolve time = 0.98 sec. (495.38 ticks) Probing time = 0.06 sec. (11.07 ticks) Clique table members: 25843. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Root relaxation solution time = 0.28 sec. (316.56 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 1335 0.0000 8656 0 0 cutoff 8659 Elapsed time = 9.52 sec. (4668.77 ticks, tree = 0.00 MB, solutions = 0) GUB cover cuts applied: 11 Clique cuts applied: 298 Cover cuts applied: 3641 Implied bound cuts applied: 784 Flow cuts applied: 2 Mixed integer rounding cuts applied: 10 Zero-half cuts applied: 179 Gomory fractional cuts applied: 2 Root node processing (before b&c): Real time = 9.55 sec. (4668.88 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) = 9.55 sec. (4668.88 ticks) ILOG.CPLEX.CpxException: CPLEX Error 1217: No solution exists. at ILOG.CPLEX.CplexI.CALL(Int32 status) at ILOG.CPLEX.CplexI.GetXcache() at ILOG.CPLEX.Cplex.GetValue(INumExpr expr) at CplexMilpManager.Implementation.CplexMilpSolver.GetValue(IVariable variable) in C:\Users\afish\Desktop\milpmanager\CplexMilpSolver\Implementation\CplexMilpSolver.cs:line 160 at IlpPlayground.Program1157221197.Start() at IlpPlayground.Env1157221197.Start() |

And surprise! There is no solution! However, if we give it a little hint, and add the following constraint:

1 |
assignedShips[0][2][0][1].Set<Equal>(solver.FromConstant(1)); |

so we say that the very first ship should be put vertically, going down, and starting in field `0,2`

, then we get the following:

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 |
Tried aggregator 3 times. MIP Presolve eliminated 57684 rows and 33893 columns. MIP Presolve modified 70292 coefficients. Aggregator did 11010 substitutions. Reduced MIP has 13391 rows, 7219 columns, and 43367 nonzeros. Reduced MIP has 6967 binaries, 252 generals, 0 SOSs, and 0 indicators. Presolve time = 0.27 sec. (197.56 ticks) Probing fixed 1581 vars, tightened 272 bounds. Probing changed sense of 84 constraints. Probing time = 0.42 sec. (128.66 ticks) Cover probing fixed 2 vars, tightened 4 bounds. Tried aggregator 3 times. MIP Presolve eliminated 5188 rows and 3247 columns. MIP Presolve modified 853 coefficients. Aggregator did 145 substitutions. Reduced MIP has 8058 rows, 3827 columns, and 23926 nonzeros. Reduced MIP has 3654 binaries, 173 generals, 0 SOSs, and 0 indicators. Presolve time = 0.09 sec. (65.93 ticks) Probing fixed 92 vars, tightened 17 bounds. Probing changed sense of 124 constraints. Probing time = 0.17 sec. (51.29 ticks) Tried aggregator 3 times. MIP Presolve eliminated 852 rows and 367 columns. MIP Presolve modified 402 coefficients. Aggregator did 13 substitutions. Reduced MIP has 7189 rows, 3447 columns, and 21604 nonzeros. Reduced MIP has 3310 binaries, 137 generals, 0 SOSs, and 0 indicators. Presolve time = 0.11 sec. (62.52 ticks) Probing fixed 146 vars, tightened 0 bounds. Probing changed sense of 26 constraints. Probing time = 0.14 sec. (42.46 ticks) Cover probing fixed 0 vars, tightened 1 bounds. Clique table members: 14708. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Root relaxation solution time = 0.09 sec. (125.71 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 971 0.0000 1352 0 0 0.0000 920 Cuts: 1897 1692 0 0 0.0000 877 Cuts: 1422 1998 0 0 0.0000 1022 Cuts: 1624 2178 * 0+ 0 0.0000 0.0000 2437 0.00% 0 0 cutoff 0.0000 0.0000 2437 0.00% Elapsed time = 2.58 sec. (1339.70 ticks, tree = 0.00 MB, solutions = 1) Clique cuts applied: 331 Cover cuts applied: 2744 Implied bound cuts applied: 968 Flow cuts applied: 3 Mixed integer rounding cuts applied: 7 Zero-half cuts applied: 20 Gomory fractional cuts applied: 7 Root node processing (before b&c): Real time = 2.58 sec. (1341.27 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) = 2.58 sec. (1341.27 ticks) ,,0_1,,,,4_1, ,,,,5_2,,, ,,,,,,, ,,,,,3_3,, ,2_2,,,,,, ,,,,,,, ,,,,1_2,,, 1 2 2 3 3 1 23 12 |

So not only it does find the solution, but also does it pretty fast.

This clearly shows that CPLEX isn’t infallible. We always need to remember that our formulas may be very correct, but the solvers may still fail us when looking for a solution.