MIP Python School Teacher Timetabling problem - 如何检查变量数是否为零等于某个数

Question

我正在尝试解决学校教师时间问题。我的情况很好，但现在我被困在如何模拟每个老师在一周内有一定数量的空闲天数，例如每个老师的零节课天数之和等于一定数

基本问题是：如何添加一个约束来计算变量等于 0.0 的次数？

y 计算老师每天教课的小时数。或多或少应该是这样的（但当然行不通）

for t in teacher:
    model += xsum( y[t, d] == 0.0 for d in day ) == 1.0

我也尝试使用变量的实际值：

for t in teacher:
    model += xsum( y[t, d].x == 0.0 for d in day ) == 1.0

和：

for t in teacher:
    model += xsum( y[t, d] for d in day if y[t, d] == 0.0 ) == 1.0

但 none 似乎有效。

我可以分享一些代码，但实际上所有内容都是用意大利语编写的，所以我试图直截了当。

Answer 1

假设您想使用（线性）MIP 求解器解决此问题，您的尝试违反了线性。以下是您可以尝试的方法：

设 y[t,d] 为教师 t 在 d 天的小时数。假设它是一个整型变量。然后我们可以定义二进制变量：

 x[t,d] = 1  if t works at d
        = 0  is t is off at d

x和y之间的link可以建模为：

 x[t,d] <= y[t,d]     (y[t,d]=0 => x[t,d]=0)
 8*x[t,d] >= y[t,d]   (y[t,d]>0 => x[t,d]=1, assuming 8 hours is the maximum per day)

现在我们可以说（用伪代码）：

 sum(d, 1-x[t,d]) = 1   (exactly one day off)

或者也许：

 sum(d, x[t,d]) = 4     (exactly 4 days at work)

Answer 2

@erwin 解决方案基于理论 POV，所以我接受它，但我无法在 MIP Python 代码中进行转换。

所以我找到了一些其他的解决方案，在某些方面并不完美，但我放在这里供其他小伙伴参考。当然，我会在翻译成英文后立即分享代码。顺便说一句，我正在寻找学术界的学术团队伙伴来撰写科学文章（@erwin？）或媒体文章或两者兼而有之，并以开源形式发布所有代码。

让我们回到问题。我找到了 3 个硬约束解决方案和 1 个软约束解决方案。我展示了所有解决方案，以便有人可以使用它

HC 解决方案 1 - 优雅的解决方案

我可以简单地为老师的组合添加一个 y[t,d] <= 0.0 的硬约束，我想在一周中的哪一天休息。

for t in self.teacher:
    for d in self.day:
        if t,d in self.desiderata:
            self.model += self.y[t, d] <= 0.0

（顺便说一句，这是一个简化版本，因为 desiderata 是一个结构化词典，但我认为你明白了）

切中要害，效果太棒了！

但我知道可以做得更好，我也可以避免使用 y[t,d] 因为它是一个导数变量所以我可以避免它并提高性能。

HC 解决方案 2 - 性能更好的解决方案

因为 y[t,d] 实际上是原始变量 x[t, g, m, d, h] 的派生变量，其中：

self.x = {
    (t, g, m, d, h): self.model.add_var(
        name="x({},{},{},{},{})".format(t, g, m, d, h),
        var_type=BINARY
    )
    for t in self.teacher
    for g in self.grade
    for m in self.matter
    for d in self.day
    for h in self.hour
}

和：

self.y = {
    (t, d): self.model.add_var(
        name="y({},{})".format(t, d),
        var_type=BINARY
    )
    for t in self.teacher
    for d in self.day
}

for t in self.teacher:
    for d in self.day:
        self.y[t,d] = xsum( self.x[t, g, m, d, h] 
                                for h in self.hour
                                for m in self.matter
                                for g in self.grade)

所以基本上，y[t,d] 总结了教师 t 在特定日期 d 工作的小时数。实际上我不需要 y[t,d] 因为我可以用这种方式直接写约束：

for t in teacher:
    for d in self.day:
        if t,d in self.desiderata:
            self.model += xsum(self.x[t, g, m, d, h] 
                               for g in self.grade 
                               for m in self.matter 
                               for h in self.hour) <= 0.0

还有 .....天哪，这也行！太棒了

这应该会带来更好的性能，因为 NP-Complete 中的问题因此减少变量数量可以减少解决时间。

但我确信我可以改进它。为什么我还要为那个老师放假的 t、d 的组合添加变量 x[t, g, m, d, h]？如果我不生成 x[t, g, m, d, h] 问题默认解决，没有任何其他限制。让我们试试：

HC 解决方案 3 - 更快的解决方案

基本上，变量 x 的生成考虑了每位教师的休息日：

self.x = {
    (t, g, m, d, h): self.model.add_var(
        name="x({},{},{},{},{})".format(t, g, m, d, h),
        var_type=BINARY
    )
    for t in self.teacher
    for g in self.grade
    for m in self.matter
    for d in self.day
    for h in self.hour
    if not (t,d in self.desiderata) # Each teacher not work in days off
}

并且在不添加任何其他限制的情况下，这也有效！！！开箱即用！

这导致我有 18% 的变量没有生成。请记住，NP-Complete 中的问题，所以这是一个巨大的改进！

所以我有 3 个不同的完全有效的硬约束解决方案，但有一个问题，因为如果休息日冲突太多，这种方法很容易导致不可行的解决方案。

有了代码，我可以一天一天地放松下来，但这样就不再是纯粹的MIP问题了。

为什么不使用 Objective 功能？

所以让我们在 Objective 函数中插入匹配的休假天数。

SC - 尽量延长休息日

为了清楚起见，我们使用 y[t,d]，但考虑到我们可以放弃它并在需要时使用 x。

self.model.objective = minimize( 
    xsum( self.y[t,d] for t in self.teacher for d in self.day if t,d in self.desiderata )
)

而且效果也很好！！！

在我将尽快分享的代码中，有一些代码优化主要是为了减少变量的数量，但概念是在上面表达的。

感谢您阅读这么长的回复。

MIP Python School Teacher Timetabling problem - 如何检查变量数是否为零等于某个数

MIP Python School Teacher Timetabling problem - how to check if the number of variables equals zero is equal to a certain number

python

optimization

scheduling