minizinc - 从一组集合中选择和求和

Question

我是 Minizinc 的新手，需要一些帮助来解决以下问题：

假设我有以下几套

int: budget= 8;
enum paths = {c1,c2,c3,c4};
array[paths] of int: size=[20,50,90,10];
array[paths] of set of int:colors=[{1,2},{3,2},{4,1,3},{4,3}];
array[paths] of set of int:cost=[{1,2},{10,8},{4,4,4},{50,12}];
array[paths] of var set of int: x; 

或者我可以通过以下方式制定它

int: budget= 8;
enum paths = {c1,c2,c3,c4};
array[paths] of int:size =[20,50,90,10];
enum colors = {w1,b2,y3,r4, h5};
array[colors] of int:cost=[2,10,50,12];
array[paths] of set of colors: s=[{w1,h5},{b2,y3,r4,},{w1,b2},{r4, h5}];

array [paths] of var set of colors: a;

所以，每条路径都有固定的大小，但我可以在颜色之间进行选择，每种颜色都有成本。因此，如果我允许为每条路径选择一种颜色，那么所有选定颜色的成本总和应该等于或低于预算。我知道如何从数组中选择或求和，而不是从一组集合中选择或求和。请问我能得到任何帮助吗？

标签： minizinc

Answer 1

使用第二个公式，您可以对变量数组求和a，并且由于它的元素是集合，您可以对这些集合进行求和，就像这样

选择颜色 constraint forall(i in paths)(card(a[i]) == 1);

对所选颜色求和 constraint sum(p in paths)( sum(c in a[p]) (cost[c]) ) < budget; 由于每组仅包含一种颜色，因此您基本上只是对整个数组求和。

编辑：
- 将 a 的定义更改为array [paths] of var colors: a;
- 确保从该路径的选项集中选择一个值
constraint forall(p in paths)(a[p] in s[p]);
- 对变量 a 的成本求和sum(p in paths)( cost[a[p]] ) <= budget;
修改后的代码如下所示。

int: budget = 20;
enum paths = {c1,c2,c3,c4};
array[paths] of int : size = [20,50,90,10];
enum colors = {w1,b2,y3,r4,h5};
array[colors] of int : cost = [2,10,50,12,4];
array[paths] of set of colors: s = [ {w1,h5}, {b2,y3,r4}, {w1,b2}, {r4,h5} ];

array [paths] of var colors: a;

constraint forall(p in paths)(a[p] in s[p]);

constraint sum(p in paths)( cost[a[p]] ) <= budget;