CPMpy 累积约束的性能问题

Question

我在使用 cpmpy 的累积约束和 ortools 求解器时遇到性能问题。尽管任务数量合理，但性能却意外下降。这是一个错误，还是有更好的方法来解决这个问题？

问题

我有一组非先发制人的任务要在给定的时间范围内完成。我的目标是确定完成这些任务所需的最少机器数量。当 X 台机器被充分利用，并且有一个单独的未分配任务比前面机器上的未使用时间总和短时，性能就会下降。

import cpmpy as cp
import logging
from typing import List


class CumulativeTestModel:
    def __init__(self, task_duration: int, nb_tasks: int, end_date: int):
        self.model: cp.Model = cp.Model()

        # Define variables
        self.objective: cp.IntVar = cp.intvar(0, nb_tasks)
        starts: List[cp.IntVar] = [cp.intvar(0, end_date) for _ in range(nb_tasks)]
        durations: List[int] = [task_duration] * nb_tasks
        ends: List[cp.IntVar] = [cp.intvar(0, end_date) for _ in range(nb_tasks)]
        demands: List[int] = [1] * nb_tasks

        # Add cumulative constraint to the model
        self.model += cp.Cumulative(
            start=starts,
            duration=durations,
            end=ends,
            demand=demands,
            capacity=self.objective,
        )

        # Minimize the objective variable
        self.model.minimize(self.objective)
        logging.info(f"Model created with {nb_tasks} tasks.")

    def run(self):
        solver = cp.model.SolverLookup.get("ortools", self.model)
        has_solution = solver.solve()

        if not has_solution:
            logging.info("No solution found.")
        else:
            logging.info(f"Solution found: {solver.status()} -> {self.objective.value()}")


if __name__ == "__main__":
    # Example usage
    CumulativeTestModel(task_duration=10, nb_tasks=3, end_date=15).run()
    CumulativeTestModel(task_duration=10, nb_tasks=11, end_date=55).run()
    CumulativeTestModel(task_duration=10, nb_tasks=21, end_date=105).run()

使用的版本：Python 3.8.10； cppy 0.9.18 ;或工具 9.8.3296 ；迷你锌 0.9.0

我尝试过的：

对不同的问题组合进行实验，观察到随着任务增加指数性能下降。

[ortools]
Model created with 3 tasks.
Solution found: ExitStatus.OPTIMAL (0.0050022 seconds) -> 3

Model created with 5 tasks.
Solution found: ExitStatus.OPTIMAL (0.006417 seconds) -> 3

Model created with 7 tasks.
Solution found: ExitStatus.OPTIMAL (0.0109515 seconds) -> 3

Model created with 9 tasks.
Solution found: ExitStatus.OPTIMAL (0.263825 seconds) -> 3

Model created with 11 tasks.
Solution found: ExitStatus.OPTIMAL (1.9085797 seconds) -> 3

Model created with 13 tasks.
-Never ends-

使用minizinc免费提供的其他求解器进行测试，不同程度地存在该问题。

[minizinc:chuffed]
Model created with 11 tasks.
Solution found: ExitStatus.OPTIMAL (0.564 seconds) -> 3

Model created with 13 tasks.
Solution found: ExitStatus.OPTIMAL (5.762 seconds) -> 3

Model created with 21 tasks.
-Never ends-

问题：

cpmpy 和 ortools 有类似的经验吗？ Bug 可能性，或者有更有效的公式吗？

感谢任何见解或指导！

Answer 1

我对累积线性松弛进行了改进，解决了这个问题：

这是输出：

Model created with 3 tasks.
Solution found: 4 -> 3 in 0.009132000000000001 s
Model created with 11 tasks.
Solution found: 4 -> 3 in 0.002023 s
Model created with 13 tasks.
Solution found: 4 -> 3 in 0.000835 s
Model created with 21 tasks.
Solution found: 4 -> 3 in 0.0011120000000000001 s