OR-Tools CP-SAT嵌套循环优化：多智能体任务调度性能问题

问题背景 #

使用OR-Tools实现智能体任务调度，从Python迁移到C++后功能正常，但在100个智能体+100个任务的场景下存在严重性能瓶颈。核心需求是最大化两个智能体间共享的任务数量（这类任务要求由2个智能体协作完成），当前通过最小化每个智能体合作的不同智能体数量间接实现目标，但现有代码中AddEquality约束的执行次数达到组合数C(100,2)*100=495000次，导致性能急剧下降，需要优化约束逻辑。

现有代码问题分析 #

现有代码为每一对智能体(a1,a2)和每个任务t创建约束：当a1、a2都执行任务t时，标记shared[{a1,a2}]为1。随后将所有shared变量求和并作为目标最小化。这种逐任务绑定的方式导致约束数量随智能体数量的平方和任务数线性增长，规模稍大就会超出求解器的处理能力。

优化方案 #

方案1：直接对准核心目标，简化约束逻辑 #

如果最终目标是最大化共享任务的总数量（每个被2个智能体完成的任务计为1次），可以直接计算该总和，无需引入大量中间布尔变量。

实现代码

LinearExpr total_shared_tasks;
for (int t = 0; t < num_tasks; ++t) {
    // 标记任务t是否为共享任务（由2个智能体完成）
    BoolVar is_shared_task = cp_model.NewBoolVar(absl::StrFormat("is_shared_task_%d", t));
    // 计算执行任务t的智能体数量
    LinearExpr agent_count_t;
    for (int a = 0; a < num_agents; ++a) {
        agent_count_t += agent_task[a][t];
    }
    // 约束：若任务是共享任务，则至少2个智能体执行；若不是共享任务，则最多1个智能体执行
    cp_model.Add(agent_count_t >= 2 * is_shared_task);
    cp_model.Add(agent_count_t <= 1 + is_shared_task);
    // 累加共享任务数
    total_shared_tasks += is_shared_task;
}
// 最大化共享任务总数
cp_model.Maximize(total_shared_tasks);

效果：约束数量从495000次降至200次（每个任务2个约束），性能提升极为显著。

方案2：保留原目标逻辑，减少约束规模 #

如果必须保留“最小化有合作关系的智能体对数量”的目标，可以将逐任务约束替换为基于智能体对的计数约束，大幅减少约束数量。

实现代码

std::vector<BoolVar> shared_pairs;

for (int a1 = 0; a1 < num_agents; ++a1) {
    for (int a2 = a1 + 1; a2 < num_agents; ++a2) {
        // 标记智能体对(a1,a2)是否有共享任务
        BoolVar has_shared = cp_model.NewBoolVar(absl::StrFormat("has_shared_%d_%d", a1, a2));
        shared_pairs.push_back(has_shared);
        
        // 计算该智能体对共同完成的任务数
        LinearExpr shared_task_count;
        for (int t = 0; t < num_tasks; ++t) {
            // 布尔变量乘积表示两个智能体是否共同执行任务t
            shared_task_count += agent_task[a1][t] * agent_task[a2][t];
        }
        
        // 约束：若共同完成任务数≥1，则标记为有共享任务；否则标记为无
        cp_model.Add(shared_task_count >= has_shared);
        cp_model.Add(shared_task_count <= num_tasks * has_shared);
    }
}

// 最小化有共享任务的智能体对数量
cp_model.Minimize(LinearExpr::Sum(shared_pairs));

效果：约束数量从495000次降至9900次（每个智能体对2个约束），性能提升明显。

关键优化思路 #

• 避免逐任务创建约束：将分散的任务级约束合并为智能体对或任务级的聚合约束，从根源上减少约束数量。
• 直接对准核心目标：绕开间接目标的转换逻辑，直接针对“最大化共享任务数”构建约束，简化求解器的计算负担。

内容的提问来源于stack exchange，提问作者jpclair