CPMpy累积约束性能优化：解决大规模任务调度中的效率瓶颈

本文探讨了使用`cpmpy`的`cumulative`约束与`ortools`求解器时，在大规模任务调度中遇到的性能瓶颈。尤其在任务数量增加时，模型求解速度显著下降。通过对`cpmpy`内部累积约束线性松弛的优化改进，该问题已得到有效解决，显著提升了求解效率，使得模型能够快速处理更多任务，从而有效支持复杂的资源调度应用。

大规模任务调度中的累积约束及其性能挑战

在资源受限的任务调度问题中，Cumulative（累积）约束是一个核心且强大的工具。它用于确保在任何给定时间点，所有正在执行任务的总资源需求不超过可用容量。例如，在机器调度场景中，它可以限制同时运行的非抢占式任务数量，以确定完成所有任务所需的最少机器数。

然而，当任务数量和时间范围增加时，这类问题往往会带来显著的计算挑战。用户在使用cpmpy库结合ortools求解器解决此类问题时，曾观察到明显的性能退化。具体表现为，当任务数量适度增加时，求解时间呈指数级增长，甚至导致模型无法在合理时间内找到解决方案。这种性能瓶颈在机器几乎完全利用，且存在少量未分配但总时长较短的任务时尤为突出。

以下是一个典型的cpmpy模型示例，用于最小化完成给定任务集所需的机器数量：

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()

        # 定义变量
        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 # 每个任务需求1单位资源

        # 添加累积约束
        # 确保在任何时间点，所有正在执行任务的总需求不超过当前机器数（self.objective）
        self.model += cp.Cumulative(
            start=starts,
            duration=durations,
            end=ends,
            demand=demands,
            capacity=self.objective,
        )

        # 最小化目标变量（机器数）
        self.model.minimize(self.objective)
        logging.info(f"Model created with {nb_tasks} tasks.")

    def run(self):
        # 使用ortools求解器
        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__":
    logging.basicConfig(level=logging.INFO)
    print("--- 原始性能测试 ---")
    CumulativeTestModel(task_duration=10, nb_tasks=3, end_date=15).run()
    CumulativeTestModel(task_duration=10, nb_tasks=5, end_date=25).run()
    CumulativeTestModel(task_duration=10, nb_tasks=7, end_date=35).run()
    CumulativeTestModel(task_duration=10, nb_tasks=9, end_date=45).run()
    CumulativeTestModel(task_duration=10, nb_tasks=11, end_date=55).run()
    # CumulativeTestModel(task_duration=10, nb_tasks=13, end_date=65).run() # 优化前会挂起
    # CumulativeTestModel(task_duration=10, nb_tasks=21, end_date=105).run() # 优化前会挂起

观察到的性能退化

在优化前的cpmpy版本中，上述模型在不同任务数量下的求解时间表现出显著差异：

任务数量	求解时间 (ortools)
3	0.005 秒
5	0.006 秒
7	0.011 秒
9	0.263 秒
11	1.908 秒
13	无法终止

从上述数据可以看出，当任务数量从9个增加到11个时，求解时间急剧上升；而当任务数量达到13个时，求解器甚至无法在合理时间内完成。即使尝试使用其他Minizinc支持的求解器（如Chuffed），也面临类似的问题，只是性能退化的具体任务数量有所不同。这表明问题并非ortools独有，而是与cpmpy对Cumulative约束的内部处理机制有关。

性能瓶颈的根源与解决方案

这种性能退化的根本原因通常在于约束传播和线性松弛的效率。在约束规划中，求解器通过传播约束来削减搜索空间。对于复杂的约束，如Cumulative，通常会利用其线性松弛（linear relaxation）来提供更强的剪枝能力。如果线性松弛不够紧密或效率低下，求解器将不得不探索更大的搜索空间，从而导致性能急剧下降。

针对这一问题，cpmpy库的开发者对Cumulative约束的线性松弛实现进行了重要的优化改进。通过增强松弛的强度和计算效率，使得求解器能够更有效地进行剪枝，从而显著减少了搜索空间。

优化后的性能表现

经过cpmpy内部优化后，Cumulative约束的性能得到了质的飞跃。以下是相同模型在优化后的cpmpy版本中运行的结果：

Model created with 3 tasks.
Solution found: 4 -> 3 in 0.009132000000000001 s
Model created with 11 tasks.
Solution found: 4 -> 3 in 0.002025 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

对比优化前后的结果，可以明显看到：