ILP Part 103 — 600 – Random IT Utensils

This is the one hundred and third 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 600. We have a squared board of nine numbers. In each cell we have one digit. We can extend each cell with one digit in the front and/or one digit at the end. Our goal is to extend numbers in a way that each row and each column sums to one hundred.

The code:

var board = new int[][]{
	new int[] { 2, 4, 9},
	new int[] { 2, 7, 3},
	new int[] { 3, 4, 3}
};

var height = board.Length;
var width = board[0].Length;

var hasPrefix = Enumerable.Range(0, height)
	.Select(row => Enumerable.Range(0, width)
		.Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()
	).ToArray();

var hasSuffix = Enumerable.Range(0, height)
	.Select(row => Enumerable.Range(0, width)
		.Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()
	).ToArray();
	
var prefix = Enumerable.Range(0, height)
	.Select(row => Enumerable.Range(0, width)
		.Select(column => solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(9)).Set<GreaterOrEqual>(solver.FromConstant(1))).ToArray()
	).ToArray();

var suffix = Enumerable.Range(0, height)
	.Select(row => Enumerable.Range(0, width).Select(column => solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(9))).ToArray()
	).ToArray();

var actualNumbers = Enumerable.Range(0, height)
	.Select(row => Enumerable.Range(0, width)
		.Select(column =>
			solver.Operation<Condition>(
				hasPrefix[row][column].Operation<Conjunction>(hasSuffix[row][column]),
				prefix[row][column].Operation<Multiplication>(solver.FromConstant(100)).Operation<Addition>(solver.FromConstant(board[row][column]).Operation<Multiplication>(solver.FromConstant(10))).Operation<Addition>(suffix[row][column]),
				solver.Operation<Condition>(
					hasPrefix[row][column],
					prefix[row][column].Operation<Multiplication>(solver.FromConstant(10)).Operation<Addition>(solver.FromConstant(board[row][column])),
					solver.Operation<Condition>(
						hasSuffix[row][column],
						solver.FromConstant(board[row][column]).Operation<Multiplication>(solver.FromConstant(10)).Operation<Addition>(suffix[row][column]),
						solver.FromConstant(board[row][column])
					)
				)
			)
		).ToArray()
	).ToArray();

// Sum rows
for(int row=0;row<height;++row){
	solver.Operation<Addition>(actualNumbers[row]).Set<Equal>(solver.FromConstant(100));
}

// Sum columns
for(int column=0;column<width;++column){
	solver.Operation<Addition>(Enumerable.Range(0, height).Select(row => actualNumbers[row][column]).ToArray()).Set<Equal>(solver.FromConstant(100));
}

solver.AddGoal("g", solver.FromConstant(0));
solver.Solve();

for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		var numberValue = (int)Math.Round(solver.GetValue(actualNumbers	[row][column]));
		
		Console.Write(numberValue + "\t");
	}
	Console.WriteLine();
}

var board = new int[][]{

new int[] { 2, 4, 9},

new int[] { 2, 7, 3},

new int[] { 3, 4, 3}

};

var height = board.Length;

var width = board[0].Length;

var hasPrefix = Enumerable.Range(0, height)

.Select(row => Enumerable.Range(0, width)

.Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()

).ToArray();

var hasSuffix = Enumerable.Range(0, height)

.Select(row => Enumerable.Range(0, width)

.Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()

).ToArray();

var prefix = Enumerable.Range(0, height)

.Select(row => Enumerable.Range(0, width)

.Select(column => solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(9)).Set<GreaterOrEqual>(solver.FromConstant(1))).ToArray()

).ToArray();

var suffix = Enumerable.Range(0, height)

.Select(row => Enumerable.Range(0, width).Select(column => solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(9))).ToArray()

).ToArray();

var actualNumbers = Enumerable.Range(0, height)

.Select(row => Enumerable.Range(0, width)

.Select(column =>

solver.Operation<Condition>(

hasPrefix[row][column].Operation<Conjunction>(hasSuffix[row][column]),

prefix[row][column].Operation<Multiplication>(solver.FromConstant(100)).Operation<Addition>(solver.FromConstant(board[row][column]).Operation<Multiplication>(solver.FromConstant(10))).Operation<Addition>(suffix[row][column]),

solver.Operation<Condition>(

hasPrefix[row][column],

prefix[row][column].Operation<Multiplication>(solver.FromConstant(10)).Operation<Addition>(solver.FromConstant(board[row][column])),

solver.Operation<Condition>(

hasSuffix[row][column],

solver.FromConstant(board[row][column]).Operation<Multiplication>(solver.FromConstant(10)).Operation<Addition>(suffix[row][column]),

solver.FromConstant(board[row][column])

)

).ToArray()

).ToArray();

// Sum rows

for(int row=0;row<height;++row){

solver.Operation<Addition>(actualNumbers[row]).Set<Equal>(solver.FromConstant(100));

}

// Sum columns

for(int column=0;column<width;++column){

solver.Operation<Addition>(Enumerable.Range(0, height).Select(row => actualNumbers[row][column]).ToArray()).Set<Equal>(solver.FromConstant(100));

}

solver.AddGoal("g", solver.FromConstant(0));

solver.Solve();

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

var numberValue = (int)Math.Round(solver.GetValue(actualNumbers [row][column]));

Console.Write(numberValue + "\t");

}

Console.WriteLine();

}

We start with creating the board in lines 1-5. Next, some helper variables in 7-8.

We then make binary flags indicating whether we extend the number or not. That’s in lines 10-18.

Next, we declare variables for the actual extensions: prefix and suffix (lines 20-27).

Now comes the main part. We calculate the real number in each cell. We check all the conditions: if we extended the number both ways, or just added the prefix, or just added the suffix, or didn’t extend at all. We then do some simple math and get the value. Lines 29-46.

Now it’s easy. We just add the condition that rows (48-51) and columns (53-56) must be equal to one hundred.

Finally, we print the solution (58-68).

Output:

Tried aggregator 4 times.
MIP Presolve eliminated 171 rows and 9 columns.
MIP Presolve modified 1359 coefficients.
Aggregator did 351 substitutions.
Reduced MIP has 735 rows, 396 columns, and 2421 nonzeros.
Reduced MIP has 270 binaries, 126 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (6.03 ticks)
Probing fixed 144 vars, tightened 211 bounds.
Probing changed sense of 27 constraints.
Probing time = 0.01 sec. (2.35 ticks)
Cover probing fixed 0 vars, tightened 161 bounds.
Tried aggregator 2 times.
MIP Presolve eliminated 441 rows and 263 columns.
MIP Presolve modified 188 coefficients.
Aggregator did 28 substitutions.
Reduced MIP has 266 rows, 105 columns, and 735 nonzeros.
Reduced MIP has 18 binaries, 87 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (1.86 ticks)
Probing time = 0.00 sec. (0.15 ticks)
Tried aggregator 1 time.
Reduced MIP has 266 rows, 105 columns, and 735 nonzeros.
Reduced MIP has 18 binaries, 87 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.32 ticks)
Probing time = 0.00 sec. (0.14 ticks)
Clique table members: 20.
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     5                      0.0000       39
      0     0        0.0000     3                    Cuts: 35       63
      0     0        0.0000     8                     Cuts: 8       79
      0     0        0.0000    35                     Cuts: 5       92
*     0+    0                            0.0000        0.0000       92    0.00%
      0     0        cutoff              0.0000        0.0000       92    0.00%
Elapsed time = 0.19 sec. (21.83 ticks, tree = 0.00 MB, solutions = 1)

Clique cuts applied:  4
Implied bound cuts applied:  25
Zero-half cuts applied:  6
Gomory fractional cuts applied:  2

Root node processing (before b&c):
  Real time             =    0.22 sec. (21.85 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.22 sec. (21.85 ticks)
22      49      29
25      37      38
53      14      33

Tried aggregator 4 times.

MIP Presolve eliminated 171 rows and 9 columns.

MIP Presolve modified 1359 coefficients.

Aggregator did 351 substitutions.

Reduced MIP has 735 rows, 396 columns, and 2421 nonzeros.

Reduced MIP has 270 binaries, 126 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.03 sec. (6.03 ticks)

Probing fixed 144 vars, tightened 211 bounds.

Probing changed sense of 27 constraints.

Probing time = 0.01 sec. (2.35 ticks)

Cover probing fixed 0 vars, tightened 161 bounds.

Tried aggregator 2 times.

MIP Presolve eliminated 441 rows and 263 columns.

MIP Presolve modified 188 coefficients.

Aggregator did 28 substitutions.

Reduced MIP has 266 rows, 105 columns, and 735 nonzeros.

Reduced MIP has 18 binaries, 87 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.01 sec. (1.86 ticks)

Probing time = 0.00 sec. (0.15 ticks)

Tried aggregator 1 time.

Reduced MIP has 266 rows, 105 columns, and 735 nonzeros.

Reduced MIP has 18 binaries, 87 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (0.32 ticks)

Probing time = 0.00 sec. (0.14 ticks)

Clique table members: 20.

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 5 0.0000 39

0 0 0.0000 3 Cuts: 35 63

0 0 0.0000 8 Cuts: 8 79

0 0 0.0000 35 Cuts: 5 92

* 0+ 0 0.0000 0.0000 92 0.00%

0 0 cutoff 0.0000 0.0000 92 0.00%

Elapsed time = 0.19 sec. (21.83 ticks, tree = 0.00 MB, solutions = 1)

Clique cuts applied: 4

Implied bound cuts applied: 25

Zero-half cuts applied: 6

Gomory fractional cuts applied: 2

Root node processing (before b&c):

Real time = 0.22 sec. (21.85 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.22 sec. (21.85 ticks)

22 49 29

25 37 38

53 14 33