ILP Part 100 — Literowce – Random IT Utensils

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:

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();

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();

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)),

)

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)),

)

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:

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()

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:

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

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:

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

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

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.