Minizinc：如何将此约束应用于调度模型？

Question

我正在研究一个调度模型，我想弄清楚如何使用这个约束：我正在使用 Minizinc 2.0.2 版本 & MinizincIDE-0.9.7-linux 和 G12-MIP & Gecode 求解器。

array[1..2,1..48] of var 0..1: table;
array[1..48] of int:demand;
array[1..2] of int: cost;
constraint forall(j in 1..48)(sum(i in 1..2)(table[i,j]) >= demand[j] );
solve minimize sum(i in 1..2)(sum(j in 1..48)(table[i,j])*cost[i]);
output [show(table)];

示例 data.dzn 文件：

demand=[0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
cost=[3,5];

使用 G12-MIP 求解器输出 Table 数组给出以下结果：

[0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

此模型适用于 2 点和 48 小时（即 2 天）。我想添加的约束是每个员工每天轮班，如果有的话，没有任何休息时间。在这个期望的输出中是：

[0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

我尝试过的方法：

var 1..5: k;
array[1..2,1..2] of var 1..48: key2;
array[1..2,1..2] of var 1..48: key1;

% My aim is to store the first and last index for which table[i,j]=1 for each point (i) for each day (k)
constraint forall(i in 1..2,j in 1..48 where k= ceil(j/24))(if 
        table[i,j]==1 then key2[i,k]=j else true endif) 
         /\ forall(i in 1..2,j in 48..1 where k= ceil(j/24))(if 
        table[i,j]==1 then key1[i,k]=j else true endif);

% make all table[i,j]=1 between first index and last index for which table[i,j]=1
constraint forall(i in 1..2,k in 1..2)(forall(t in key1[i,k]..key2[i,k])(table[i,t]=1));

当我运行它通过 Linux 终端使用这个命令时：mzn-g12mip test.mzn data.dzn 它给出了与之前相同的结果。当我运行通过 MinizincIDE-0.9.7-linux 它给出了这个错误：

MiniZinc: type error: type error in operator application for `..'. No matching operator found with left-hand side type `var int' and right-hand side type `var int'

这段代码有什么问题吗？或者有其他方法可以满足这个约束吗？

Answer 1

两个注意事项：

我得到了与您相同的结果：运行通过命令行可以正常工作。使用 MiniZincIDE 会出现同样的错误，但是在终端中重置 MZN_STDLIB_DIR 后运行 MiniZincIDE.sh 然后它就可以工作了。你有MZN_STDLIB_DIR设置吗？然后尝试用这个命令重置它。

     export MZN_STDLIB_DIR=

关于shift约束，大概可以用全局约束"regular"。有关示例，请参见 MiniZinc 教程。您在这里想要的特定约束是 "contiguity" 约束，它要求收集所有 1。它不是内置在 MiniZinc 中，但您可以查看我的模型作为示例：http://hakank.org/minizinc/contiguity_regular.mzn

这是我的模型版本，包括连续性的定义。

include "globals.mzn"; 

array[1..2,1..48] of var 0..1: table;
array[1..48] of int:demand;
array[1..2] of int: cost;

var int: z = sum(i in 1..2)(sum(j in 1..48)(table[i,j])*cost[i]);

constraint forall(j in 1..48)(sum(i in 1..2)(table[i,j]) >= demand[j] );

constraint
  forall(i in 1..2) (
    contiguity([table[i,j] | j in 1..48])
  )
;

predicate contiguity(array[int] of var int: a) =
  let {
        int: n_states = 3,
        int: input_max = 2,
        int: initial_state = 1,
        set of int: accepting_states = {1,2,3},
        % the transition matrix
        array[1..n_states, 1..input_max] of int: transition_fn =
    array2d(1..n_states, 1..input_max,
    [ 
      % note:all states are accepting states
      1,2, % state 1 (start): input 0 -> state 1, input 1 -> state 2 i.e. 0*
      3,2, % state 2: 1* 
      3,0, % state 3: 0* 
    ]),
      int: len = length(a),
      % note: regular cannot handle 0 values, it must be > 0
      array[1..len] of var 1..2: reg_input
  } in
   forall(i in 1..len) (
     reg_input[i] = a[i] + 1
   )
   /\
   regular(reg_input, n_states, input_max, transition_fn,
                    initial_state, accepting_states)
;


solve minimize z;

output [
  "table: ", show(table), "\n",
  "z: ", show(z), "\n",
]
++ ["\ntable:"] ++
[
  if j = 1 then "\n" else " " endif ++
    show(table[i,j])
  | i in 1..2, j in 1..48
]
;

demand=[0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
cost=[3,5];

使用此模型的最佳解决方案与您的解决方案不同，因为如果人 1 必须完成强制任务之间的所有 "empty" 任务，则没有任何需求的任务成本太高。如果您有一些其他约束不允许这种任务分离，则必须将其添加到模型中。

table:
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Minizinc：如何将此约束应用于调度模型？

Minizinc: How to apply this constraint for scheduling model?

constraint-programming

minizinc