ORtools 为每个学生分配一个普通或三个特殊类

Question

在我的问题中，我有学生需要分配 classes。他们要么被分配一个常规 class，要么被分配三个特殊 class。我有列表 students 和 classes，对应于学生和 class 时间表：

students = [s0,s1,s2,s3,s4,s5,s6,s7,s8,s9]
classes = [sp0,sp1,sp2,sp3,sp4,sp5,sp6,r0,r1,r2,r3,r4,r5,r6]

其中前 7 个 class 是特殊的 classes（一个学生分配了其中的三个），最后 7 个是常规的 classes（一个学生被分配了其中之一）。基本设置如下所示：

def main():
    # Data.
    num_students = len(students)
    num_classes = len(classes)
    all_students = range(num_students)
    all_classes = range(num_classes)
    k = 7
    special_classes = range(k) # k = number of special classes
    regular_classes = range(k,num_classes)

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

    # Creates scheduling variables.
    # sched[(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))

但现在我需要一个约束，以便为每个学生分配一个常规 class 或三个特殊 class es。我在想：

for s in all_students:

        # either a student is assigned 3 special classes or 1 regular
        model.AddBoolOr([sum(sched[(c,s)] for c in other_classes)==1,
                        sum(sched[(c,s)] for c in special_classes)==3])

        # either a student is assigned 0 special classes or 3
        model.AddBoolOr([sum(sched[(c,s)] for c in special_classes)==0,
                        sum(sched[(c,s)] for c in special_classes)==3])

        # either a student is assigned 1 regular class or 0
        model.AddBoolOr([sum(sched[(c,s)] for c in other_classes)==1,
                        sum(sched[(c,s)] for c in other_classes)==0])

但我意识到我不能像这样使用 AddBoolOr。

你认为我可以怎样解决这个问题？

感谢任何帮助！

Answer 1

您可以为每个学生使用一个中间布尔值：

for s in all_students:
    regular = model.NewBoolVar('reg_%i' % s)
    model.Add(sum(sched[(c,s)] for c in regular_classes) == 1).OnlyEnforceIf(regular)
    model.Add(sum(sched[(c,s)] for c in special_classes) == 0).OnlyEnforceIf(regular)

    model.Add(sum(sched[(c,s)] for c in regular_classes) == 0).OnlyEnforceIf(regular.Not())
    model.Add(sum(sched[(c,s)] for c in special_classes) == 3).OnlyEnforceIf(regular.Not())

请查看 https://github.com/google/or-tools/blob/stable/ortools/sat/doc/channeling.md 以了解有关在 ortools 中建模的更多信息。

ORtools 为每个学生分配一个普通或三个特殊类

ORtools assigning either one regular or three special classes to each student

python

algorithm

scheduling

or-tools

ORtools 为每个学生分配一个普通或三个特殊 类

ORtools assigning either one regular or three special classes to each student

python

algorithm

scheduling

or-tools

ORtools 为每个学生分配一个普通或三个特殊类