在带有数组集的 minizinc 中使用 forall（不连续）

Question

我正在尝试使用 forall 实例来添加约束，但我遇到了这个错误，我不确定我应该怎么做。

(array slice must be contiguous) in call 'forall' in array comprehension expression with i = {10,24} in binary '<=' operator expression in call 'slice_1d'

我正在处理一个调度问题，我需要应用一个限制来确定一组任务（由 suc 确定）只能在特定任务（由 1..nTasks 确定）已经完成后开始.

模型如下

include "globals.mzn";
int: n_res;
array [1..n_res] of int: res_cap;
int: n_tasks;
array [1..n_tasks] of int: duration;
array [1..n_res, 1..n_tasks] of int: res_req;
array [1..n_tasks] of set of int: suc;
int: t_max = sum(i in 1..n_tasks)(duration[i]);
array [1..n_tasks] of var 0..t_max: start;
array [1..n_tasks] of var 0..t_max: end;
var 0..t_max: makespan;

% constraint that I can't implement. this constraint should make every task[i] to start after a set of tasks{i} are finished. The set is defined by the array suc.

constraint forall (i in suc)(end[i] <= start[i]);

constraint cumulative(start, duration, row(res_req, 1), res_cap[1]);
constraint cumulative(start, duration, row(res_req, 2), res_cap[2]);
constraint cumulative(start, duration, row(res_req, 3), res_cap[3]);
constraint cumulative(start, duration, row(res_req, 4), res_cap[4]);

constraint forall(i in 1..n_tasks)(end[i] = start[i]+duration[i]);
constraint makespan = max(i in 1..n_tasks)(end[i]);

solve minimize makespan;

数组 suc 和 1..nTasks 的行数相同。

我有一个一维数组，其中包含可以在任务 [i] 结束后开始的特定任务集。

在一个较小的实例中，例如：成功 = [{5, 15}, {17, 23, 28}, {10, 12}, {8}]

我需要实现的是：

end[i] | i in 1..nTasks <= start[i] | i in suc

对于我发布的特定集合，可以像这样手动完成：

 end[1] <= start[5]
 end[1] <= start[15]
 end[2] <= start[17]
 end[2] <= start[23]
 end[2] <= start[28]
 end[3] <= start[10]
 end[3] <= start[12]
 end[4] <= start[8]

我刚开始使用 minizinc，有些东西告诉我我遗漏了一些可能很简单的东西，但是，已经有一段时间了，我无法实现它。

我如何编写可以执行此操作的 forall 实例？

Answer 1

罪魁祸首是这个约束（如错误所示）：

constraint forall (i in suc)(end[i] <= start[i]);

您尝试使用 suc 作为循环的生成器。问题是您需要为该约束做两件事：当前任务的开始应该在该任务的后续任务之前。使用您的方法这是不可能的，因为 i 将具有诸如 { 10, 24 } 之类的值，但是当前任务没有值（参考）（即 start[i] 的值）。

这里有一个解决方法：用i in n_res循环遍历所有任务（i是第i个任务），然后循环遍历suc[i]得到每个任务的后续任务。

constraint forall (i in 1..n_res) (
    forall(s in suc[i]) (         
        end[i] <= start[s]
    )
);

另一种可能更简单的方法是将两个 forall 循环合并为一个循环：

constraint forall (i in 1..n_res, s in suc[i]) (
   end[i] <= start[s]
);

当我运行模型时，它生成了这个解决方案：

% obj = 51
start = array1d(1..30, [7, 21, 4, 31, 6, 41, 34, 3, 35, 39, 21, 28, 47, 0, 38, 48, 44, 35, 28, 7, 10, 34, 11, 47, 41, 3, 11, 3, 22, 17]);
end = array1d(1..30, [17, 25, 5, 34, 11, 51, 35, 7, 41, 47, 28, 35, 51, 3, 48, 51, 48, 38, 35, 12, 11, 44, 19, 48, 47, 7, 18, 9, 31, 21]);
makespan = 51;
----------
% obj = 51
==========

在带有数组集的 minizinc 中使用 forall（不连续）

Using forall in minizinc with an array set (not contiguous)

minizinc