c++ 在OR-Tools CP-SAT中优化嵌套循环

wj8zmpe1  于 12个月前  发布在  其他
关注(0)|答案(1)|浏览(101)

我们使用OR-Tools为代理生成一个任务调度表,起初是用Python,现在是用C++。
我们的代码产生了所需的结果,但我们遇到了性能问题。目标是最大化2个代理之间共享的任务数(在将代理数设置为2的情况下定义的任务上)。该算法通过最小化每个代理与之合作的不同代理数来运行,这比最大化每个代理共享的任务数更有效。

std::vector<BoolVar> shared_sums;
std::map<std::pair<int, int>, BoolVar> shared;

for (int a1 = 0; a1 < num_agents; ++a1)
{
  for (int a2 = a1 + 1; a2 < num_agents; ++a2)
  {
    for (int t = 0; t < num_tasks; ++t)
    {
      // ... code here to continue if task done by one agent

      cp_model.AddEquality(shared[{a1, a2}], 1)
      .WithName(absl::StrFormat("ct_eq_shared_%d_%d_%d", a1, a2, t))
          .OnlyEnforceIf({agent_task[a2][t], agent_task[a1][t]}); // agent_task[a1][t] BoolVar
    }
    shared_sums.push_back(shared[{a1, a2}]);
  }
}

cp_model.AddEquality(total_shared_sum, LinearExpr::Sum(shared_sums)).WithName("ct_eq_total_shared_sum");
cp_model.Minimize(total_shared_sum);

字符串
我的问题是,对于100个代理和100个任务,我的AddEquality约束将被应用C(100,2)* 100次,这在性能方面是灾难性的。
我可以实施什么解决方案来优化此约束?
非常感谢

hs1rzwqc

hs1rzwqc1#

只需编写一个流模型:每个(代理,任务)1个boolvar assign每个代理1个容量每个任务1个计数var域[1,2]

for all agent: sum(assign(agent, task) * duration(task) for all task) <= capacity(agent))
  for all task: sum(assign(agent, task) for all agent) == count(task))

字符串
那么目标就是

minimize(sum(count(task) for all tasks - num_tasks))

相关问题