python - 添加要求数字落在上限和下限之间的约束(或工具约束优化/CP)

Question

问题的关键:“关于如何在 CP 模型的 ortools 中最适本地编码此约束，有什么想法吗？”

<小时/>

我试图解决的问题有点像此处概述的员工调度问题:

https://developers.google.com/optimization/scheduling/employee_scheduling

问题

我想制定一个类作业计划，在一段时间内每天将学生分配到教室(现在，接下来的两年每周一次)。

我有一所学校，有 8 个教室。学生根据年龄被分配到教室。每个教室都有一个与之相关的年龄范围 - 例如:

• 一类:1-3岁
• 2类:2-4岁
• 3级:3-5岁，等等

请注意，教室的年龄范围确实重叠。

学生应被分配到具有以下限制的教室:

• 1) 每个学生每天必须被分配到 1 个教室
• 2) 一个教室的学生总数不得超过该教室的最大容纳人数
• 3) 每个学生必须被分配到适合其年龄的教室
• 4) 一旦学生转到较高的教室(例如从 2 类转到 3 类)，他们就不能再回到较低的教室

这是我的数据:

学生 = 列表列表；每个列表包含 1 名学生的信息:(例如，

students = [['学生 ID', '出生日期', 'classroom_index'], ...]

哪里:

• “学生 ID”= 每个学生的唯一 ID
• “出生日期”= 日期对象，并且
• 'classroom_index' = 学生当前的类作业(1、2、3 等)

教室 = 列表列表；每个列表包含有关 1 个教室的信息:(例如，

教室 = [['classroom_index', 'ageMin', 'ageMax', 'capacity']...]

地点:

• 'classroom_index' = 每个教室的唯一 ID(即 1-8)，
• 'ageMin' = 进入教室的最低年龄(以岁为单位的整数)
• 'ageMax' = 进入教室的最大年龄(以岁为单位的整数)，以及
• “容量”= 任意一天可分配到教室的最大学生人数

日期 = 涵盖预测时间表期间的日期列表；在本例中，预测时间表考虑了 future 2 年内的每个星期一:

日期 = [2019/11/25, 2019/12/2, ...]

当前状态:

按照上面链接的员工调度代码的结构，这就是我所拥有的:

声明模型

model = cp_model.CpModel()

创建变量

classroom_assignments = {}

for i, d in enumerate(dates):
  for s in students:
    for c in classrooms:
      classroom_assignments[(i, s[0], c[0])] = model.NewBoolVar('classroom_assignments_i%is%ic%i' % (i, s[0], c[0]))

将学生分配到教室

## The sum of students assigned to a classroom each day must be <= the capacity of that classroom
for i, d in enumerate(dates):
  for c in classrooms:
    model.Add(sum(classroom_assignments[(i, s[0], c[0])] for s in students) <= c[3])

## The sum of classrooms that a student is assigned to each day must be exactly 1
for s in students:
  for i, d in enumerate(dates):
    model.Add(sum(classroom_assignments[(i, s[0], c[0])] for c in classrooms) == 1)

## The sum of classrooms that a student is assigned to each day where the student's age is outside the min/max range for the classroom must be exactly 0
for s in students:
  for i, d in enumerate(dates):
    d_diff = dateutil.relativedelta.relativedelta(d, s[1])
    age = (d_diff.years * 12)
    model.Add(sum(classroom_assignments[(d, s[0], c[0])] for c in classrooms) == 1 if c[1] <= age and c[2] >= age)

上面的最后一个 for 循环是我尝试定义约束#3，它抛出错误:

  File "<ipython-input-65-205499abc4dd>", line 15
    model.Add(sum(classroom_assignments[(d, s[0], c[0])] for c in classrooms) == 1 if c[1] <= age_months and c[2] >= age_months)
                                                                                                                               ^
SyntaxError: invalid syntax

关于如何在 CP 模型的 ortools 中最适本地编码此约束有什么想法吗？

我尝试提供尽可能多的相关信息，但如果您需要其他信息或说明，请告诉我。

Answer 1

看起来像一个简单的语法错误，您的理解过滤器位于错误的范围内。

model.Add(
    sum(
        classroom_assignments[(d, s[0], c[0])]
        for c in classrooms
        if c[1] <= age_months and c[2] >= age_months
    )
    == 1
)