标签: cp-sat

我正在构建一个具有一组复杂约束的轮班调度程序，并且为此使用 CP-SAT 求解器。我有一个像这样的数组：

    num_vals = 3
    for n in all_employees:
        for d in all_timeslots:
            shifts[(n, d)] = model.NewIntVar(0, num_vals - 1, 'shift_n%id%i' % (n, d))

我试图设置一个约束，其中 5 个 IntVar 值的后续行的乘积始终等于零，所以我使用如下所示的内容：

        sq_r = model.NewIntVar(0, 1,'sq_r')
        for wind in range(0,11):
            model.AddMultiplicationEquality(sq_r, [shifts[(n, wind)], shifts[(n, wind+1)], shifts[(n, wind+2)], shifts[(n, wind+3)], shifts[(n, wind+4)]])

但我收到以下错误：

Check failed: vars.size() == 2 (5 vs. 2) General int_prod not supported yet.
*** Check failure stack trace: ***
    @   00007FF98D2B8C45  PyInit__pywrapsat
    @   00007FF98D2B6F82  PyInit__pywrapsat
    @   00007FF98D550E50  PyInit__pywrapsat
    @   00007FF98D54D8FF …

我使用 Google OR Tools in Python 编写了一个约束编程模型，它使用 CP 求解器。我需要多次运行该模型，并且在每次运行中我都会修改约束。目前，每次我想运行模型时，我都会从头开始创建模型对象。无论如何，我可以修改现有模型的变量/约束，这样我就不需要每次都从头开始构建模型吗？

为了提供更好的上下文，请考虑以下示例模型。

from ortools.sat.python import cp_model
model = cp_model.CpModel()
num_vals = 3
a = model.NewIntVar(0, num_vals -1, 'a')
b = model.NewIntVar(0, num_vals -1, 'b')
c = model.NewIntVar(0, num_vals -1, 'c')
model.Add(a == b)
solver = cp_model.CpSolver()
solver.Solve(model)

现在，在问题的第二次运行中，我想做以下更改。

1. 将变量 c 的上限更改为5
2. 删除约束a==b
3. 创建新约束a==c

在不从头开始构建模型的情况下如何实现这一目标？

python 中的or-tools模块添加了自定义语法，其中函数可以采用任意表达式作为参数（如下所示），该语法不是立即求值，而是稍后作为约束解决

model.Add(x + 2 * y -1 >= z)

当我从函数中打印参数的类型时，它显示

<class 'ortools.sat.python.cp_model.BoundedLinearExpression'>

一种简单的方法是将表达式作为字符串传递，但感觉更好。我想了解这是如何实现的。这是在 python 中创建自定义语法的方法吗？是否需要更新解析器或类似的东西？

这是简单的程序

from ortools.sat.python import cp_model


def foo(expr):
    print(expr, type(expr))

def main():
    model = cp_model.CpModel()
    var_upper_bound = max(50, 45, 37)
    x = model.NewIntVar(0, var_upper_bound, 'x')
    y = model.NewIntVar(0, var_upper_bound, 'y')
    z = model.NewIntVar(0, var_upper_bound, 'z')
    a = 0
    b = 0
    c = 0

    model.Add(2*x + 7*y + 3*z == 50)

    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:
        print('x value: ', …

我的团队正在构建一个 CP-SAT 求解器，该求解器可以在一段时间内安排作业（例如家庭作业），并且可用性可变（可用于完成作业的时间）。我们正在努力加速我们的模型。

我们尝试了 num_search_workers 和其他参数调整，但想检查其他速度的提高。目标是在 5-10 秒内解决约 100 天的问题和最多 2000 个作业（以 M1 mac 为基准）。有任何想法吗？

问题描述：按照这些要求在 d 天内布置作业

• 一天的分配时间不得超过当天的可用时间
• 应尊重赋值依赖性（如果 A 需要 B，则 B 不应出现在 A 之后）
• 作业可以分开（以便更好地适应时间很少的日子）
• 针对一天中任务类型的多样性进行优化

# 天和 # 个作业后，解决问题的速度显着减慢。这是预料之中的，但我们想知道您是否可以提出可能的加速建议

这是一个单元测试示例。希望能够展示拆分、排序和时间限制。

days = [{"secondsAvailable": 1200}, {"secondsAvailable": 1200}, {"secondsAvailable": 1200}, {"secondsAvailable": 1200}]
assignments = [
    {"id": 1, "resourceType": "Type0", "seconds": 2400, "deps": [], "instances": 2},
    {"id": 2, "resourceType": "Type0", "seconds": 1200, "deps": [1], "instances": 1},
    {"id": 3, "resourceType": "Type0", "seconds": 1200, "deps": [1, 2], "instances": 1},
    ]
result …