2

我正在研究一个调度模型，我想弄清楚如何使用这个约束：我正在使用 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 求解器的输出表数组给出以下结果：

[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'

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

4

1 回答 1

1

两个注意事项：

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

     export MZN_STDLIB_DIR=

关于移位约束，您可能可以使用全局约束“常规”。有关示例，请参阅 MiniZinc 教程。您在此处需要的特定约束是“连续性”约束，它要求收集所有 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 必须在强制任务之间执行所有“空”任务，那么没有任何需求的任务成本太高。如果您有其他一些不允许这种任务分离的约束，则必须在模型中添加它。

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
于 2015-06-05T06:29:43.460 回答