Minizinc Objective 函数用于计划中的间隙

Question

我有一个有效的 Miniznic 模型来安排 1 位教授和 n 名学生 () 的个别课程。该模型考虑可用性（硬约束）以及教授的时间偏好（objective 函数）作为学生。

现在，我想扩展模型并优化时间表，以便课程之间的差距被最小化。

示例：

  Schedule  : p L p p L L . . p p L L p L L p L p p . L p L L . L p L
  Real Gaps : . L p p L L . . . . L L p L L p L . . . L p L L . L p L

哪里

 `p` =  0 == Teacher available, but no Lesson
 `L` =  1 == Teacher gives lesson (to student)
 `.` = -1 == Teacher not available

显然，插槽1中的p不能算作间隙。相似地，插槽 9 和 10 也没有间隙。消除所有错误的差距， Schedule 最终应该看起来像 Real Gaps 数组（注意：false 间隙用 . 标记；与 not available 相同).

结果将是一个间隙数组 [2, 1, 1, 1, 1]（每个间隙显示它持续的槽数）。基于这样的数组，然后可以例如制定一个 objective 以最小化总间隙槽。

在 ruby 中，我能够制定一个算法来满足我的要求：

def gap_array(schedule_arr)
  # initialize variables
  start_search = false              # flag for break start
  break_slots  = 0                  # counter of break slots
  res_arr      = []                 # resulting array
  schedule_arr.each do |slot|
    if slot == 1                    # start watching for break
      start_search = true
    end
    #
    if start_search                 
      if    slot == 0               # == break
        break_slots += 1
      elsif slot == 1               # == consecutive lesson slot
        if break_slots > 0          # number of break_slots > 0
          res_arr.append(break_slots)
          break_slots = 0
        end
      else                          # == not available
        break_slots  = 0            # any break so far is discarded
        start_search = false         
      end
    end
  end
  return res_arr
end

如何在 Minizinc 中制定这样的算法？

谢谢！

Answer 1

在 MiniZinc 中实现此目的的一种方法是按以下方式在扩展模型：

最初将 teacher_free 计算为教师不在的位置与没有上课的相邻位置相结合（这是分两步完成的，从左边 teacher_free_left 和右边teacher_free_right，分别，然后合并结果形成teacher_free).

在下一步中，real_gap 被计算为教师没有空闲且没有上课的时段。

在 objective 中引入了 real_gap 的惩罚项，例如（k2 是间隙惩罚权重）：

int: k2 = 1;
var int: obj = sum(s in STUDENT, t in TIME)
    (active[s,t] * (prio_time[s,t] + k*prioTeacher_time[t])) - k2*sum(real_gap);

这里是模型的所有其他扩展（还有一些进一步的评论）：

array[DAY,SLOT]           of var 0..1: lesson = array2d(DAY, SLOT, [sum(s in STUDENT)(active[s,time(d,z)]) | d in DAY, z in SLOT]);
array[DAY,SLOT]           of var 0..1: teacher_free_left;
array[DAY,SLOT]           of var 0..1: teacher_free_right;
array[DAY,SLOT]           of var 0..1: teacher_free;
array[DAY,SLOT]           of var 0..1: real_gap;

predicate equals_and(var 0..1: z, var 0..1: x, var 0..1: y) = 
    (z <= x /\ z <= y /\ z >= x + y - 1);

predicate equals_or(var 0..1: z, var 0..1: x, var 0..1: y) = 
    (z >= x /\ z >= y /\ z <= x + y);

% calculate teacher free left
%    first slot -> teacher free = no lesson in the slot
%    other slots -> teacher free = teacher out or (left slot teacher free and no lesson in slot)
array[DAY,SLOT]           of var 0..1: teacher_free_left_temp;

constraint forall(d in DAY)
    (teacher_free_left_temp[d,1]=1-lesson[d,1]);
    
constraint forall(d in DAY, z in 2..maxSlots)
    (equals_and(teacher_free_left_temp[d,z], teacher_free_left[d,z-1], 1-lesson[d,z]));

constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free_left[d,z], 1 - bool2int(z in teacher[d]), teacher_free_left_temp[d,z]));
    
% calculate teacher free right
%    last slot -> teacher free = no lesson in the slot
%    other slots -> teacher free = teacher out or (right slot teacher free and no lesson in slot)
array[DAY,SLOT]           of var 0..1: teacher_free_right_temp;

constraint forall(d in DAY)
    (teacher_free_right_temp[d,maxSlots]=1-lesson[d,maxSlots]);
    
constraint forall(d in DAY, z in 1..maxSlots-1)
    (equals_and(teacher_free_right_temp[d,z], teacher_free_right[d,z+1], 1-lesson[d,z]));

constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free_right[d,z], 1 - bool2int(z in teacher[d]), teacher_free_right_temp[d,z]));

% teacher free when teacher free left or teacher free right
constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free[d,z], teacher_free_left[d,z], teacher_free_right[d,z]));

% real gap when teacher not free and no lesson
constraint forall(d in DAY, z in SLOT)
   (equals_and(real_gap[d,z], 1-teacher_free[d,z], 1-lesson[d,z]));

Minizinc Objective 函数用于计划中的间隙

Minizinc Objective Function For Gaps in Schedule

minizinc

objective-function