ILP Part 88 — Magical Tangram – Random IT Utensils

This is the eightieth eighth 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 this task. We have a board with some letters on it. Letters are assigned numbers from zero to nine. Letters are connected with lines. Spaces inside regions have numbers which indicate what’s the biggest difference between two directly connected letters on the side of the region. Also, the biggest difference may appear only once on the side.

Solution:

var letters = new Dictionary<char, IVariable>();
for(char c = 'a'; c <= 'j'; ++ c){
	letters[c] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(9));
}

Action<char[], int> createDifferences = (chars, maxDifference) => {
	var vars = chars.Select(c => letters[c]).ToArray();
	
	var diffs = new List<IVariable>();
	for(int i=0;i<chars.Length;++i){
		var a = vars[i];
		var b = vars[(i+1)%chars.Length];
		var difference = a.Operation<Subtraction>(b).Operation<AbsoluteValue>();
		diffs.Add(difference);
	}
	
	var less = new List<IVariable>();
	foreach(var d in diffs){
		d.Set<LessOrEqual>(solver.FromConstant(maxDifference));
		less.Add(d.Operation<IsEqual>(solver.FromConstant(maxDifference)));
	}
	
	solver.Operation<Addition>(less.ToArray()).Set<Equal>(solver.FromConstant(1));
};

createDifferences(new []{'a', 'b', 'd', 'f'}, 5);
createDifferences(new []{'b', 'e', 'g', 'd'}, 4);
createDifferences(new []{'b', 'c', 'e'}, 3);
createDifferences(new []{'f', 'd', 'h', 'i'}, 4);
createDifferences(new []{'d', 'g', 'h'}, 3);
createDifferences(new []{'g', 'e', 'c', 'j'}, 5);
createDifferences(new []{'g', 'j', 'i', 'h'}, 5);

var allVars = solver.Set<AllDifferent>(letters.Values.First(), letters.Values.Skip(1).ToArray());


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

for(char c = 'a'; c <= 'j'; ++ c){
	Console.WriteLine(c + " - " + solver.GetValue(letters[c]));
}

var letters = new Dictionary<char, IVariable>();

for(char c = 'a'; c <= 'j'; ++ c){

letters[c] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(9));

}

Action<char[], int> createDifferences = (chars, maxDifference) => {

var vars = chars.Select(c => letters[c]).ToArray();

var diffs = new List<IVariable>();

for(int i=0;i<chars.Length;++i){

var a = vars[i];

var b = vars[(i+1)%chars.Length];

var difference = a.Operation<Subtraction>(b).Operation<AbsoluteValue>();

diffs.Add(difference);

}

var less = new List<IVariable>();

foreach(var d in diffs){

d.Set<LessOrEqual>(solver.FromConstant(maxDifference));

less.Add(d.Operation<IsEqual>(solver.FromConstant(maxDifference)));

}

solver.Operation<Addition>(less.ToArray()).Set<Equal>(solver.FromConstant(1));

};

createDifferences(new []{'a', 'b', 'd', 'f'}, 5);

createDifferences(new []{'b', 'e', 'g', 'd'}, 4);

createDifferences(new []{'b', 'c', 'e'}, 3);

createDifferences(new []{'f', 'd', 'h', 'i'}, 4);

createDifferences(new []{'d', 'g', 'h'}, 3);

createDifferences(new []{'g', 'e', 'c', 'j'}, 5);

createDifferences(new []{'g', 'j', 'i', 'h'}, 5);

var allVars = solver.Set<AllDifferent>(letters.Values.First(), letters.Values.Skip(1).ToArray());

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

solver.Solve();

for(char c = 'a'; c <= 'j'; ++ c){

Console.WriteLine(c + " - " + solver.GetValue(letters[c]));

}

First, we create variables for letters in line 1-4. Next, we define a helper function which calculates differences between connected letters (9-15), then it makes sure that all differences are not greater than the allowed maximum (19) and counts how many differences are equal to the maximum. Finally, it makes sure that exactly one difference is equal to the maximum (line 23).

Next, we create regions in lines 26-32. And we also make sure that all letters are different (line 34).

Output:

Tried aggregator 2 times.
MIP Presolve eliminated 354 rows and 116 columns.
MIP Presolve modified 1047 coefficients.
Aggregator did 182 substitutions.
Reduced MIP has 570 rows, 308 columns, and 1748 nonzeros.
Reduced MIP has 272 binaries, 36 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (3.35 ticks)
Probing fixed 52 vars, tightened 0 bounds.
Probing changed sense of 45 constraints.
Probing time = 0.00 sec. (2.25 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 104 rows and 52 columns.
MIP Presolve modified 52 coefficients.
Aggregator did 97 substitutions.
Reduced MIP has 369 rows, 159 columns, and 1138 nonzeros.
Reduced MIP has 123 binaries, 36 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (1.24 ticks)
Probing time = 0.00 sec. (0.31 ticks)
Tried aggregator 1 time.
Reduced MIP has 369 rows, 159 columns, and 1138 nonzeros.
Reduced MIP has 123 binaries, 36 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (0.55 ticks)
Probing time = 0.00 sec. (0.31 ticks)
Clique table members: 33.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.01 sec. (0.54 ticks)

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

      0     0        0.0000    59                      0.0000       91
      0     0        0.0000    28                     Cuts: 7       97
      0     0        0.0000    55                    Cuts: 29      136
      0     0        0.0000    17                 ZeroHalf: 4      148
      0     0        0.0000    29                    Cuts: 12      155
      0     2        0.0000    11                      0.0000      155
Elapsed time = 0.17 sec. (40.77 ticks, tree = 0.01 MB, solutions = 0)
*  3959    87      integral     0        0.0000        0.0000    44362    0.00%

Cover cuts applied:  1
Implied bound cuts applied:  34
Mixed integer rounding cuts applied:  3
Zero-half cuts applied:  26
Gomory fractional cuts applied:  9

Root node processing (before b&c):
  Real time             =    0.17 sec. (40.58 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.47 sec. (129.14 ticks)
  Sync time (average)   =    0.10 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.64 sec. (169.72 ticks)
a - 9
b - 4
c - 1
d - 8
e - 2
f - 6
g - 5
h - 7
i - 3
j - 0

Tried aggregator 2 times.

MIP Presolve eliminated 354 rows and 116 columns.

MIP Presolve modified 1047 coefficients.

Aggregator did 182 substitutions.

Reduced MIP has 570 rows, 308 columns, and 1748 nonzeros.

Reduced MIP has 272 binaries, 36 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (3.35 ticks)

Probing fixed 52 vars, tightened 0 bounds.

Probing changed sense of 45 constraints.

Probing time = 0.00 sec. (2.25 ticks)

Tried aggregator 2 times.

MIP Presolve eliminated 104 rows and 52 columns.

MIP Presolve modified 52 coefficients.

Aggregator did 97 substitutions.

Reduced MIP has 369 rows, 159 columns, and 1138 nonzeros.

Reduced MIP has 123 binaries, 36 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (1.24 ticks)

Probing time = 0.00 sec. (0.31 ticks)

Tried aggregator 1 time.

Reduced MIP has 369 rows, 159 columns, and 1138 nonzeros.

Reduced MIP has 123 binaries, 36 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (0.55 ticks)

Probing time = 0.00 sec. (0.31 ticks)

Clique table members: 33.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.01 sec. (0.54 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 59 0.0000 91

0 0 0.0000 28 Cuts: 7 97

0 0 0.0000 55 Cuts: 29 136

0 0 0.0000 17 ZeroHalf: 4 148

0 0 0.0000 29 Cuts: 12 155

0 2 0.0000 11 0.0000 155

Elapsed time = 0.17 sec. (40.77 ticks, tree = 0.01 MB, solutions = 0)

* 3959 87 integral 0 0.0000 0.0000 44362 0.00%

Cover cuts applied: 1

Implied bound cuts applied: 34

Mixed integer rounding cuts applied: 3

Zero-half cuts applied: 26

Gomory fractional cuts applied: 9

Root node processing (before b&c):

Real time = 0.17 sec. (40.58 ticks)

Parallel b&c, 8 threads:

Real time = 0.47 sec. (129.14 ticks)

Sync time (average) = 0.10 sec.

Wait time (average) = 0.00 sec.

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

Total (root+branch&cut) = 0.64 sec. (169.72 ticks)

a - 9

b - 4

c - 1

d - 8

e - 2

f - 6

g - 5

h - 7

i - 3

j - 0