Search code examples
constraint-programmingminizincoperations-researchset-cover

Why does this two-line change break this minizinc set-cover program?


The program below (adapted from http://www.hakank.org/minizinc/set_covering4b.mzn ) is a solution to the set-cover problem (example data provided at end of question). This runs correctly.

int: num_alternatives;
int: num_objects;
par set of int: ALTERNATIVES = 1..num_alternatives;

% costs for the alternatives
array[ALTERNATIVES] of int: costs; 

% objects covered by the alternatives
array[ALTERNATIVES] of var set of 1..num_objects: a;

% decision variable: which alternative to choose
array[ALTERNATIVES] of var bool: x; 

% the objective to minimize
var int: z = sum(i in 1..num_alternatives) (x[i]*costs[i]); 
solve minimize z;

constraint
   forall(j in 1..num_objects) (
     sum(i in 1..num_alternatives) (x[i] * bool2int(j in a[i])) >= 1
   )
;

output
[
  "x: " ++ show(x) ++ "\n" ++ 
  "a: " ++ show(a) ++ "\n"
];

However, if I replace the a definition above:

array[ALTERNATIVES] of var set of 1..num_objects: a;

with these two lines that seem to me to be equivalent:

var set of int: OBJECTS = 1..num_objects;  
array[ALTERNATIVES] of OBJECTS: a;

...suddenly I get the following error:

MiniZinc: type error: type-inst must be par set but is `var set of int'

This confuses me. What did I even change? In each case a is an array of sets of ints. The type-instance is a var set of int in each case, but the second one throws an error and the first one doesn't for some reason?


Here's some data which can be dropped in the bottom of the .mzn code file to produce a self-contained, runnable example:

% data
num_alternatives =  10;
costs = [ 19, 16, 18, 13, 15, 19, 15, 17, 16, 15];
num_objects = 8;

% the alternatives and the objects they contain
a = [
  {1,6},
  {2,6,8},
  {1,4,7},
  {2,3,5},
  {2,5},
  {2,3},
  {2,3,4},
  {4,5,8},
  {3,6,8},
  {1,6,7}
];

Solution

  • You could write it as follows:

    int: num_alternatives;
    int: num_objects;
    set of int: ALTERNATIVES = 1..num_alternatives;
    set of int: OBJECTS = 1..num_objects;
    
    % costs for the alternatives
    array[ALTERNATIVES] of int: costs; 
    
    % objects covered by the alternatives
    array[ALTERNATIVES] of var set of OBJECTS: a;
    
    % decision variable: which alternative to choose
    array[ALTERNATIVES] of var bool: x; 
    
    % the objective to minimize
    var int: z = sum(i in ALTERNATIVES) (x[i]*costs[i]); 
    solve minimize z;
    
    constraint
       forall(j in OBJECTS) (
         sum(i in ALTERNATIVES) (x[i] * (j in a[i])) >= 1
       )
    ;
    
    output
    [
      "x: " ++ show(x) ++ "\n" ++ 
      "a: " ++ show(a) ++ "\n"
    ];
    

    In your experiment

    var set of int: OBJECTS = 1..num_objects;  
    array[ALTERNATIVES] of OBJECTS: a;
    

    a is an array of integers in the range 1..num_objects. But you intended an array of sets of integers in that range.