CODEWITHSUNDEEP
minizinc
jan06
jan06

Reputation: 79

Minizinc search 2d array with constraints

How could I select the smallest number from each row of a 2d array while making sure the same column can at most be selected twice (in the following case, for row 1, column 5 is chosen; for row 2, column 5 is chosen while for row 3, column 5 can no longer be selected, so column 2 is selected as the min): (Besides, in java, it is often that ArrayList is used to add and remove elements but how is it possible to do this in Minizinc using constraints)?

int: m = 3;
int: n = 5;
array[1..m,1..n] of int: diffs = [|14,18,24,30,13
                                  |10,12,18,24,7
                                  | 8,7,12,18,6|]

Upvotes: 2

Views: 5926

Answers (1)

hakank
hakank

Reputation: 6854

Below is one approach which minimize the sum of the difference between the values of the selected columns and the "real" smallest values of each row.

include "globals.mzn"; 
int: m = 3;
int: n = 5;
array[1..m,1..n] of int: diffs = [|14,18,24,30,13
                                  |10,12,18,24,7
                                  | 8,7,12,18,6|];

% decision variables
array[1..m] of var 1..n: x; % which row to select
var int: z; % difference between the selected and smallest values

solve minimize z;
% solve satisfy;

% constraint 1: at_most 2 of the same column can be selected
constraint
  % at most two rows can have the same column
  forall(j in 1..n) (
    at_most(2,x,j)
  )
; 

% constraint 2: calculate the least difference
constraint
  % get smallest difference to the smallest value
  z = sum(i in 1..m) (
       % value of selected column - the smallest value of the row
       diffs[i,x[i]]-min([diffs[i,j] | j in 1..n]) 
  )
  % /\ % for solve satisfy
  % z = 1
  ;

  output [
    "z: \(z)\n",
    "x: \(x)  values:\([diffs[i,x[i]] | i in 1..m])\n"
  ];

For this problem instance there are two optimal solutions with z=1, i.e. the solution is 1 larger than the "real" optimal value (which would have been without the max 2 column constraint).

 z: 1 
 x: [5, 5, 2]  values:[13, 7, 7]
 ----------
 z: 1 
 x: [1, 5, 5]  values:[14, 7, 6]

The first solution mean that we pick the values from column 5 for the 2 first rows (i.e. the values of 13 and 7), and for the third row we pick the value from column 2 (i.e. 7). This happens to be the solution mentioned in the example.

There is an alternative approach where constraint 2 is replaced with the following constraint, i.e. which sums the selected values directly (and not the difference against minimum value of each row):

% constraint 2: calculate the least difference
constraint
  z = sum([diffs[i,x[i]] | i in 1..m])
  % /\ % for solve satisfy
  % z = 27
;

It has - of course - the same solution of columns. The difference is only in the value of "z":

z: 27 
x: [5, 5, 2]  values:[13, 7, 7]
---------
z: 27 
x: [1, 5, 5]  values:[14, 7, 6]

Arguably this later variant is neater, but if the values in the "diffs" matrix are large then the first variant should probably be used since solvers tend to be happier to work with smaller values. (For matrices with large values it's recommended to use a restricted domain of "z" instead of "var int", but I'm a little lazy tonight. :-)

Upvotes: 2

Related Questions