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

wj8zmpe1 于 12个月前发布在其他

关注(0)|答案(1)|浏览(100)

我们使用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次，这在性能方面是灾难性的。
我可以实施什么解决方案来优化此约束？
非常感谢

c++

来源：https://stackoverflow.com/questions/77764808/optimizing-nested-loops-in-or-tools-cp-sat

1条答案

按热度按时间

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

型

赞(0）回复(0）举报 12个月前

我来回答

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

1条答案

相关问题

热门标签

最新问答