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}
];
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.