ORtools 安排学生类有冲突的时间表

Question

在我的问题中，我有学生每个人都需要分配给一个 class。每个学生和每个 class 都有一个时间表，如果一个学生被分配到一个 class，时间表不能冲突。

举个小例子，假设有五个时间块。如果学生的日程安排在第三个时间段已满，但所有其他时间段均空闲，则他们的日程安排将类似于 [0,0,1,0,0]。类似地，如果 class 发生在第一次和第二次时间块上，它的时间表将看起来像 [1,1,0,0,0]。因为这个学生的日程与这个class的日程不冲突，所以可以把这个学生分配到这个class。但是，如果学生的日程安排是 [1,0,0,0,0]，则无法将他们分配到 class。

使用 google 的 ortools，约束看起来很简单：每个学生只有一个 class，如果我们有 2 个学生时间表 S 和 3 个 class 时间表 C：

S = {0:[0,0,1,0,0],1:[0,1,0,1,0]}
C = {0:[1,1,0,0,0],1:[0,0,1,0,1],2:[1,0,0,0,0]}

然后学生 [i] 只有在 np.dot(np.asarray(S[s]),np.asarray(C[c]))==0 才能分配给 class [j]，即时间表的点积为零。

实施后一个约束对我没有用。我尝试了以下方法：

num_students = 2
    num_classes = 3
    all_students = range(num_students)
    all_classes = range(num_classes)

    S = {0:[0,0,1,0,0],1:[0,1,0,1,0]}
    C = {0:[1,1,0,0,0],1:[0,0,1,0,1],2:[1,0,0,0,0]}

    # Creates the model.
    model = cp_model.CpModel()

    # Creates scheduling variables.
    # shifts[(c, s)]: student c is assigned to class s.
    # 1 if true, 0 if not
    sched = {}
    for s in all_students:
        for c in all_classes:
                sched[(c,s)] = model.NewBoolVar('shift_c%is%i' % (c, s))

    # Each class is assigned to exactly one student in the schedule period.
    for s in all_students:
        model.Add(sum(sched[(c, s)] for c in all_classes) == 1)

    # The schedules cannot conflict
    for c in all_classes:
        for s in all_students:
            model.AddBoolOr([(sched[(c,s)] and np.dot(np.asarray(S[s]),np.asarray(C[c]))==0),
                            sched[(c,s)].Not()])

但是，当我运行这样做时，出现以下错误：

<ipython-input-41-9aad6f1c8113> in main()
     55         for s in all_students:
     56             model.AddBoolOr([(sched[(c,s)] and np.dot(np.asarray(S[s]),np.asarray(C[c]))==0),
---> 57                             sched[(c,s)].Not()])
     58 
     59 

/anaconda3/lib/python3.6/site-packages/ortools/sat/python/cp_model.py in AddBoolOr(self, literals)
   1162         model_ct = self.__model.constraints[ct.Index()]
   1163         model_ct.bool_or.literals.extend(
-> 1164             [self.GetOrMakeBooleanIndex(x) for x in literals])
   1165         return ct
   1166 

/anaconda3/lib/python3.6/site-packages/ortools/sat/python/cp_model.py in <listcomp>(.0)
   1162         model_ct = self.__model.constraints[ct.Index()]
   1163         model_ct.bool_or.literals.extend(
-> 1164             [self.GetOrMakeBooleanIndex(x) for x in literals])
   1165         return ct
   1166 

/anaconda3/lib/python3.6/site-packages/ortools/sat/python/cp_model.py in GetOrMakeBooleanIndex(self, arg)
   1408         else:
   1409             raise TypeError('NotSupported: model.GetOrMakeBooleanIndex(' +
-> 1410                             str(arg) + ')')
   1411 
   1412     def GetIntervalIndex(self, arg):

TypeError: NotSupported: model.GetOrMakeBooleanIndex(True)

这只是重新格式化 AddBoolOr 语句的问题，还是我遗漏了更大的东西？

感谢任何帮助！

Answer 1

您不能将 min, max, or, and 用于 ortools 创建的变量。
AddBoolOr 只需要 BoolVars。

针对您的问题，您可以执行以下操作之一：

固定值

if np.dot(np.asarray(S[s]),np.asarray(C[c])) != 0:
    model.Add(sched[(c,s)] == 0)

不创建布尔值如果 np.dot(np.asarray(S[s]),np.asarray(C[c]))!=0

ORtools 安排学生类有冲突的时间表

ORtools scheduling students to classes with conflicting schedules

python

algorithm

scheduling

or-tools

ORtools 安排学生 类 有冲突的时间表

ORtools scheduling students to classes with conflicting schedules

python

algorithm

scheduling

or-tools

ORtools 安排学生类有冲突的时间表