我们使用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次,这在性能方面是灾难性的。
我可以实施什么解决方案来优化此约束?
非常感谢
1条答案
按热度按时间hs1rzwqc1#
只需编写一个流模型:每个(代理,任务)1个boolvar
assign
每个代理1个容量每个任务1个计数var域[1,2]字符串
那么目标就是
型