minizinc

Max Value from 2D array of var float

I wanted to complete the laplace.mzn example provided in the MiniZinc Tutorial without looking at the code. My original attempt, shown in Code Block 1 below, provides the correct answer. I wanted to try to generalize the output statement by making the hardcoded value of 6 in the show_float() function, which specifies that every float in the output should be right-justified with 6 digits, dynamic (i.e. find the max value in t and base the output width off of that.

My first attempt was to add the statement in Code Block 2, but I received the following error:

MiniZinc: evaluation error: 
laplace.mzn:28:
in variable declaration for 'm'
  in call 'max'
  /home/str/MiniZinc/share/minizinc/std/builtins.mzn:278:
  in let expression
  /home/str/MiniZinc/share/minizinc/std/builtins.mzn:281:
  in call 'max_t'
  /home/str/MiniZinc/share/minizinc/std/builtins.mzn:2020:
  in if-then-else expression
  /home/str/MiniZinc/share/minizinc/std/builtins.mzn:2023:
  in let expression
  /home/str/MiniZinc/share/minizinc/std/builtins.mzn:2025:
  in call 'array_float_maximum'
  /home/str/MiniZinc/share/minizinc/linear/redefinitions-2.0.mzn:16:
  in if-then-else expression
  /home/str/MiniZinc/share/minizinc/linear/redefinitions-2.0.mzn:19:
  in call 'array_float_minimum_I'
  /home/str/MiniZinc/share/minizinc/linear/redefinitions.mzn:108:
  in let expression
  /home/str/MiniZinc/share/minizinc/linear/redefinitions.mzn:110:
    with i = 1
  in call 'ub'
  cannot determine bounds

Then, though I wasn't happy about how it looked, I tried Code Block 3, which resulted in the following error:

MiniZinc: evaluation error: 
  /home/str/MiniZinc/share/minizinc/linear/redefs_lin_reifs.mzn:319: 
  in if-then-else expression 
  /home/str/MiniZinc/share/minizinc/linear/redefs_lin_reifs.mzn:321: 
  in call 'ub' 
  cannot determine bounds

Any suggestions on how to obtain the max value from 't' after the constraint problem has been satisfied?

Code Block 1:

int: w = 5;
int: h = 5;

array[1..h,1..w] of var float: t;
float: top = 100.0;
float: bottom = 0.0;
float: left = 0.0;
float: right = 0.0;
float: corners = 0.0;

% Top row all the same except corners
constraint forall(c in 2..w-1)(t[1,c] = top);

% Bottom row all the same except corners
constraint forall(c in 2..w-1)(t[h,c] = bottom);

% First column all the same except corners
constraint forall(r in 2..h-1)(t[r,1] = left);

% Last column all the same except corners
constraint forall(r in 2..h-1)(t[r,w] = right);

% The four corners must be the same value
constraint t[1,1] = corners /\ t[1,1] = t[1,w] /\ t[1,w] = t[h,w] /\ t[h,w] = t[h,1];

constraint forall( r in 2..h-1, c in 2..w-1)( 4*t[r,c] = t[r-1,c] + t[r+1,c] + t[r,c-1] + t[r,c+1]);

solve satisfy;

output[ show_float(6,2,t[r,c]) ++
        if c = h then "\n" else " " endif
        | r in 1..h, c in 1..w ];

Code Block 2:

var float: m = max(r in 1..h, c in 1..w)(t[r,c]);

Code Block 3:

% Width of temperature grid
int: w = 5;

% Height of temperature grid
int: h = 5;

array[1..h,1..w] of var float: t;

% Temperature in the top row, bottom row, left row, right row, and corners
float: top = 100.0;
float: bottom = 0.0;
float: left = 0.0;
float: right = 0.0;
float: corners = 0.0;

% Top row all the same except corners
constraint forall(c in 2..w-1)(t[1,c] = top);

% Bottom row all the same except corners
constraint forall(c in 2..w-1)(t[h,c] = bottom);

% First column all the same except corners
constraint forall(r in 2..h-1)(t[r,1] = left);

% Last column all the same except corners
constraint forall(r in 2..h-1)(t[r,w] = right);

% The four corners must be the same value
constraint t[1,1] = corners /\ t[1,1] = t[1,w] /\ t[1,w] = t[h,w] /\ t[h,w] = t[h,1];

constraint forall( r in 2..h-1, c in 2..w-1)( 4*t[r,c] = t[r-1,c] + t[r+1,c] + t[r,c-1] + t[r,c+1]);

% Get the maximum value in t
var float: m;
constraint forall(r in 1..h, c in 1..w)(m >= t[r,c]);
constraint exists(r in 1..h, c in 1..w)(m = t[r,c]);

solve maximize m;

% Wish to replace the value six in the next line with m + 3, where the 3 represents
% character for the 2 digits to the right of a decimal point and 1 character for the
% decimal point
output[ show_float(6,2,t[r,c]) ++
        if c = h then "\n" else " " endif
        | r in 1..h, c in 1..w ];
Solution

  • The cannot determine bounds error is from the MIP solver what I can see. It's caused by the definition of t and m as a var float in the model. It can be fixed with some fix - and fairly small - domain for these decision variables. E.g.

    var 0.0..100.0: m;
array[1..h,1..w] of var 0.0..100.0: t;

    If you run with a FlatZinc solver that can handle floats as decision variables (e.g. Gecode or JaCoP) then this error is not thrown. However, Gecode is slow since the two decision variables t and m are defined as var float which are huge domains. If you set a specific - and fairly small - domain, e.g. 0.0..100.0 then Gecode is fast for this problem. Or at least state that t and m should be larger or equal to 0 (not as fast since the domain is much larger than 0..100). Note that the JaCoP solver don't have this problem; it's not very slow with var float.