ILP Part 75 — 100 and 13 – Random IT Utensils

This is the seventieth fifth 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 are going to solve 100 and 13. We have a board with numbers and we need to find a path with given amount of numbers, with some specific sum, and where all numbers are different. First, data model:

public class Field{
	public int Value {get;set;}
	public IVariable Selected {get;set;}
	public IVariable Up {get;set;}
	public IVariable Down {get;set;}
	public IVariable Left {get;set;}
	public IVariable Right {get;set;}
	public IVariable[] AllDirections { get { return new IVariable[]{Up, Down, Left, Right}; } }
	public IVariable DirectionsCount {get;set;}
	public IVariable Identifier {get;set;}	
}

public class Field{

public int Value {get;set;}

public IVariable Selected {get;set;}

public IVariable Up {get;set;}

public IVariable Down {get;set;}

public IVariable Left {get;set;}

public IVariable Right {get;set;}

public IVariable[] AllDirections { get { return new IVariable[]{Up, Down, Left, Right}; } }

public IVariable DirectionsCount {get;set;}

public IVariable Identifier {get;set;}

}

And now the solution:

var board = new int[][]{
	new int[]{2, 5, 11, 4, 6},
	new int[]{10, 14, 9, 15, 6},
	new int[]{7, 15, 9, 8, 1},
	new int[]{8, 11, 1, 3, 10},
	new int[]{3, 14, 13, 5, 2}
};		
var sum = 100;
var length = 13;


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

// Create fields
var fields = board.Select(r => r.Select(c => new Field{
	Value = c,
	Selected = solver.CreateAnonymous(Domain.BinaryInteger),
	Up = solver.CreateAnonymous(Domain.BinaryInteger),
	Down = solver.CreateAnonymous(Domain.BinaryInteger),
	Left = solver.CreateAnonymous(Domain.BinaryInteger),
	Right = solver.CreateAnonymous(Domain.BinaryInteger),
	Identifier = solver.CreateAnonymous(Domain.PositiveOrZeroInteger)
}).ToArray()).ToArray();

// Block invalid directions
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		if(row == 0)fields[row][column].Up.Set<Equal>(solver.FromConstant(0));
		if(row == height - 1)fields[row][column].Down.Set<Equal>(solver.FromConstant(0));
		if(column == 0)fields[row][column].Left.Set<Equal>(solver.FromConstant(0));
		if(column == width - 1)fields[row][column].Right.Set<Equal>(solver.FromConstant(0));
	}
}

// Match direction neighbours
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		if(row > 0)fields[row][column].Up.Set<Equal>(fields[row-1][column].Down);
		if(row < height - 1)fields[row][column].Down.Set<Equal>(fields[row+1][column].Up);
		if(column > 0)fields[row][column].Left.Set<Equal>(fields[row][column-1].Right);
		if(column < height - 1)fields[row][column].Right.Set<Equal>(fields[row][column+1].Left);
	}
}

// Set Selected properly
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		fields[row][column].Selected.Set<Equal>(solver.Operation<Disjunction>(fields[row][column].AllDirections));
	}
}

// Set path continuous
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		fields[row][column].DirectionsCount = solver.Operation<Addition>(fields[row][column].AllDirections);
		fields[row][column].DirectionsCount.Set<LessOrEqual>(solver.FromConstant(2));
	}
}

// Set path with start an end
solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => f.DirectionsCount).ToArray()).Set<Equal>(solver.FromConstant((length - 2)*2 + 2));
		
// Set path length
solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => f.Selected).ToArray()).Set<Equal>(solver.FromConstant(length));

// Set path sum
solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => solver.Operation<Condition>(f.Selected, solver.FromConstant(f.Value), solver.FromConstant(0))).ToArray()).Set<Equal>(solver.FromConstant(sum));

// Set different values on the path
{
	IVariable[] parts = fields.SelectMany(r => r).Select(f => solver.Operation<Condition>(f.Selected, solver.FromConstant(f.Value), solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<GreaterOrEqual>(solver.FromConstant(100)).Set<LessOrEqual>(solver.FromConstant(width*height - length + 100)))).ToArray();
	solver.Set<AllDifferent>(parts[0], parts.Skip(1).ToArray());
}

// Propagate identifiers
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		List<Tuple<IVariable, IVariable>> neighbours = new List<Tuple<IVariable, IVariable>>();
		
		Field self = fields[row][column];
		
		if(row > 0)neighbours.Add(Tuple.Create(fields[row-1][column].Identifier, self.Up));
		if(row < height - 1)neighbours.Add(Tuple.Create(fields[row+1][column].Identifier, self.Down));
		if(column > 0)neighbours.Add(Tuple.Create(fields[row][column-1].Identifier, self.Left));
		if(column < width - 1)neighbours.Add(Tuple.Create(fields[row][column+1].Identifier, self.Right));
		
		
		foreach(var n in neighbours){
			var difference = self.Identifier.Operation<Subtraction>(n.Item1).Operation<AbsoluteValue>();
			
			n.Item2.Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));
		}
		
		foreach(var n1 in neighbours){
			foreach(var n2 in neighbours){
				if(n1.Item1 == n2.Item1)continue;
				var difference = n1.Item1.Operation<Subtraction>(n2.Item1).Operation<AbsoluteValue>();
				n1.Item2.Operation<Conjunction>(n2.Item2).Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(2))).Set<Equal>(solver.FromConstant(1));
			}
		}
	}
}

solver.Solve();

for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		Console.Write(solver.GetValue(fields[row][column].Selected) + ",");
	}
	Console.WriteLine();
}
Console.WriteLine();

100

101

102

103

104

105

106

107

108

109

110

111

112

113

var board = new int[][]{

new int[]{2, 5, 11, 4, 6},

new int[]{10, 14, 9, 15, 6},

new int[]{7, 15, 9, 8, 1},

new int[]{8, 11, 1, 3, 10},

new int[]{3, 14, 13, 5, 2}

};

var sum = 100;

var length = 13;

var height = board.Length;

var width = board[0].Length;

// Create fields

var fields = board.Select(r => r.Select(c => new Field{

Value = c,

Selected = solver.CreateAnonymous(Domain.BinaryInteger),

Up = solver.CreateAnonymous(Domain.BinaryInteger),

Down = solver.CreateAnonymous(Domain.BinaryInteger),

Left = solver.CreateAnonymous(Domain.BinaryInteger),

Right = solver.CreateAnonymous(Domain.BinaryInteger),

Identifier = solver.CreateAnonymous(Domain.PositiveOrZeroInteger)

}).ToArray()).ToArray();

// Block invalid directions

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

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

if(row == 0)fields[row][column].Up.Set<Equal>(solver.FromConstant(0));

if(row == height - 1)fields[row][column].Down.Set<Equal>(solver.FromConstant(0));

if(column == 0)fields[row][column].Left.Set<Equal>(solver.FromConstant(0));

if(column == width - 1)fields[row][column].Right.Set<Equal>(solver.FromConstant(0));

}

// Match direction neighbours

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

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

if(row > 0)fields[row][column].Up.Set<Equal>(fields[row-1][column].Down);

if(row < height - 1)fields[row][column].Down.Set<Equal>(fields[row+1][column].Up);

if(column > 0)fields[row][column].Left.Set<Equal>(fields[row][column-1].Right);

if(column < height - 1)fields[row][column].Right.Set<Equal>(fields[row][column+1].Left);

}

// Set Selected properly

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

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

fields[row][column].Selected.Set<Equal>(solver.Operation<Disjunction>(fields[row][column].AllDirections));

}

// Set path continuous

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

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

fields[row][column].DirectionsCount = solver.Operation<Addition>(fields[row][column].AllDirections);

fields[row][column].DirectionsCount.Set<LessOrEqual>(solver.FromConstant(2));

}

// Set path with start an end

solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => f.DirectionsCount).ToArray()).Set<Equal>(solver.FromConstant((length - 2)*2 + 2));

// Set path length

solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => f.Selected).ToArray()).Set<Equal>(solver.FromConstant(length));

// Set path sum

solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => solver.Operation<Condition>(f.Selected, solver.FromConstant(f.Value), solver.FromConstant(0))).ToArray()).Set<Equal>(solver.FromConstant(sum));

// Set different values on the path

{

IVariable[] parts = fields.SelectMany(r => r).Select(f => solver.Operation<Condition>(f.Selected, solver.FromConstant(f.Value), solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<GreaterOrEqual>(solver.FromConstant(100)).Set<LessOrEqual>(solver.FromConstant(width*height - length + 100)))).ToArray();

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

}

// Propagate identifiers

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

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

List<Tuple<IVariable, IVariable>> neighbours = new List<Tuple<IVariable, IVariable>>();

Field self = fields[row][column];

if(row > 0)neighbours.Add(Tuple.Create(fields[row-1][column].Identifier, self.Up));

if(row < height - 1)neighbours.Add(Tuple.Create(fields[row+1][column].Identifier, self.Down));

if(column > 0)neighbours.Add(Tuple.Create(fields[row][column-1].Identifier, self.Left));

if(column < width - 1)neighbours.Add(Tuple.Create(fields[row][column+1].Identifier, self.Right));

foreach(var n in neighbours){

var difference = self.Identifier.Operation<Subtraction>(n.Item1).Operation<AbsoluteValue>();

n.Item2.Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));

}

foreach(var n1 in neighbours){

foreach(var n2 in neighbours){

if(n1.Item1 == n2.Item1)continue;

var difference = n1.Item1.Operation<Subtraction>(n2.Item1).Operation<AbsoluteValue>();

n1.Item2.Operation<Conjunction>(n2.Item2).Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(2))).Set<Equal>(solver.FromConstant(1));

}

solver.Solve();

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

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

Console.Write(solver.GetValue(fields[row][column].Selected) + ",");

}

Console.WriteLine();

}

Console.WriteLine();

First, we define the riddle in lines 1-9, and couple helper variables in 12-13.

Next, we create fields in lines 16-24. Value is just the number in the field. Selected indicates whether the field is chosen to the final result. Up and other directions are for indicting whether path continues in some specific direction from this field. Identifier is to propagate numbers throughout the path to make sure we have only one path on the board.

First, we block invalid directions in lines 26-34. We want to make sure that we don’t step out of the board.

Next, in lines 36-44 we make sure that if some field thinks that path is going in some direction then the neighbour thinks the same.

Next, we make sure that if there is a path in the field then it must be selected (lines 46-51).

Next, we make sure the path is continuous (lines 53-59). This means that it cannot fork so it can go in at most two directions in given field.

Next, we indicate the path has a start and an end (line 62). This is actually not needed as we block forks but better safe than sorry.

We set path length (line 65) and sum of the numbers (line 68).

Next, we make sure that all numbers on the path are different. In lines 71-74 we take all variables and check their SelectedIdentifier to set this constraint, given field must differ from its neighbours by one, and its neighbours must differ by two. This effectively makes creating loops impossible.

Finally, solution:

Tried aggregator 2 times.
MIP Presolve eliminated 2694 rows and 888 columns.
MIP Presolve modified 8814 coefficients.
Aggregator did 2484 substitutions.
Reduced MIP has 7203 rows, 3808 columns, and 21521 nonzeros.
Reduced MIP has 3415 binaries, 393 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.09 sec. (48.76 ticks)
Probing fixed 70 vars, tightened 50 bounds.
Probing changed sense of 325 constraints.
Probing time = 0.05 sec. (9.71 ticks)
Cover probing fixed 0 vars, tightened 50 bounds.
Tried aggregator 2 times.
MIP Presolve eliminated 304 rows and 193 columns.
MIP Presolve modified 1900 coefficients.
Aggregator did 300 substitutions.
Reduced MIP has 6599 rows, 3315 columns, and 19898 nonzeros.
Reduced MIP has 2922 binaries, 393 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.05 sec. (20.59 ticks)
Probing time = 0.05 sec. (4.77 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 100 rows and 50 columns.
Reduced MIP has 6499 rows, 3265 columns, and 19598 nonzeros.
Reduced MIP has 2872 binaries, 393 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.05 sec. (13.46 ticks)
Probing time = 0.03 sec. (3.85 ticks)
Clique table members: 13256.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.06 sec. (54.46 ticks)

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

      0     0        0.0000    61                      0.0000      913
      0     0        0.0000   212                   Cuts: 509     1471
      0     0        0.0000   265                   Cuts: 554     1990

Repeating presolve.
Tried aggregator 1 time.
MIP Presolve eliminated 2554 rows and 1527 columns.
Reduced MIP has 3945 rows, 1738 columns, and 11809 nonzeros.
Reduced MIP has 1473 binaries, 265 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (10.44 ticks)
Probing time = 0.02 sec. (2.67 ticks)
Tried aggregator 1 time.
Reduced MIP has 3945 rows, 1738 columns, and 11809 nonzeros.
Reduced MIP has 1473 binaries, 265 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (4.85 ticks)
Represolve time = 0.06 sec. (23.96 ticks)
Probing time = 0.01 sec. (2.67 ticks)
Clique table members: 7703.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.08 sec. (47.44 ticks)

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

      0     0        0.0000    76                      0.0000     2868
      0     0        0.0000   142                   Cuts: 459     3911
      0     0        0.0000   141                    Cuts: 84     4355
      0     2        0.0000    22                      0.0000     4355
Elapsed time = 4.05 sec. (1387.34 ticks, tree = 0.01 MB, solutions = 0)
     15    17        0.0000   194                      0.0000     9806
*    32+   15                            0.0000        0.0000    18968    0.00%

GUB cover cuts applied:  33
Clique cuts applied:  144
Cover cuts applied:  20
Implied bound cuts applied:  287
Mixed integer rounding cuts applied:  8
Zero-half cuts applied:  41
Gomory fractional cuts applied:  8

Root node processing (before b&c):
  Real time             =    4.05 sec. (1385.51 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.89 sec. (441.92 ticks)
  Sync time (average)   =    0.56 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    4.94 sec. (1827.43 ticks)
1,1,1,1,1,
1,0,0,0,0,
1,1,1,0,0,
0,0,1,0,0,
1,1,1,0,0,

Tried aggregator 2 times.

MIP Presolve eliminated 2694 rows and 888 columns.

MIP Presolve modified 8814 coefficients.

Aggregator did 2484 substitutions.

Reduced MIP has 7203 rows, 3808 columns, and 21521 nonzeros.

Reduced MIP has 3415 binaries, 393 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.09 sec. (48.76 ticks)

Probing fixed 70 vars, tightened 50 bounds.

Probing changed sense of 325 constraints.

Probing time = 0.05 sec. (9.71 ticks)

Cover probing fixed 0 vars, tightened 50 bounds.

Tried aggregator 2 times.

MIP Presolve eliminated 304 rows and 193 columns.

MIP Presolve modified 1900 coefficients.

Aggregator did 300 substitutions.

Reduced MIP has 6599 rows, 3315 columns, and 19898 nonzeros.

Reduced MIP has 2922 binaries, 393 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.05 sec. (20.59 ticks)

Probing time = 0.05 sec. (4.77 ticks)

Tried aggregator 1 time.

MIP Presolve eliminated 100 rows and 50 columns.

Reduced MIP has 6499 rows, 3265 columns, and 19598 nonzeros.

Reduced MIP has 2872 binaries, 393 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.05 sec. (13.46 ticks)

Probing time = 0.03 sec. (3.85 ticks)

Clique table members: 13256.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.06 sec. (54.46 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 61 0.0000 913

0 0 0.0000 212 Cuts: 509 1471

0 0 0.0000 265 Cuts: 554 1990

Repeating presolve.

Tried aggregator 1 time.

MIP Presolve eliminated 2554 rows and 1527 columns.

Reduced MIP has 3945 rows, 1738 columns, and 11809 nonzeros.

Reduced MIP has 1473 binaries, 265 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (10.44 ticks)

Probing time = 0.02 sec. (2.67 ticks)

Tried aggregator 1 time.

Reduced MIP has 3945 rows, 1738 columns, and 11809 nonzeros.

Reduced MIP has 1473 binaries, 265 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (4.85 ticks)

Represolve time = 0.06 sec. (23.96 ticks)

Probing time = 0.01 sec. (2.67 ticks)

Clique table members: 7703.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.08 sec. (47.44 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 76 0.0000 2868

0 0 0.0000 142 Cuts: 459 3911

0 0 0.0000 141 Cuts: 84 4355

0 2 0.0000 22 0.0000 4355

Elapsed time = 4.05 sec. (1387.34 ticks, tree = 0.01 MB, solutions = 0)

15 17 0.0000 194 0.0000 9806

* 32+ 15 0.0000 0.0000 18968 0.00%

GUB cover cuts applied: 33

Clique cuts applied: 144

Cover cuts applied: 20

Implied bound cuts applied: 287

Mixed integer rounding cuts applied: 8

Zero-half cuts applied: 41

Gomory fractional cuts applied: 8

Root node processing (before b&c):

Real time = 4.05 sec. (1385.51 ticks)

Parallel b&c, 8 threads:

Real time = 0.89 sec. (441.92 ticks)

Sync time (average) = 0.56 sec.

Wait time (average) = 0.00 sec.

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

Total (root+branch&cut) = 4.94 sec. (1827.43 ticks)

1,1,1,1,1,

1,0,0,0,0,

1,1,1,0,0,

0,0,1,0,0,

1,1,1,0,0,