OR工具安排学生安排上课时间有冲突的课程

Question

在我的问题中，我有一些学生，每个学生都需要分配给一个班级。每个学生和每个班级都有时间表，如果将学生分配到班级，则时间表不会冲突。

作为一个玩具示例，说有五个时间块。如果在第三个时间段填写了学生的时间表，但在其他所有时间都没有，则他们的时间表将看起来像[0,0,1,0,0]。同样，如果在第一时间块和第二时间块上进行某个类，则其时间表将类似于[1,1,0,0,0]。由于该学生的日程安排与该课程的日程安排没有冲突，因此可以将该学生分配给该课程。但是，如果学生的时间表为[1,0,0,0,0]，则无法将其分配给班级。

使用Google的ortools，约束看起来很简单：每个学生只有一个班级，并且如果我们有2个学生时间表S和3个课程时间表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]，即时间表的点积为零，才可以将学生[j]分配到班级np.dot(np.asarray(S[s]),np.asarray(C[c]))==0。

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

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则不要创建布尔值！= 0