python - or-tools:小问题在 cpp 中不可行,但在 python 中有效
问题描述
我在优化问题中遇到了一个问题,在该问题中,简单可行的约束导致我的 cpp 程序在尝试解决时返回“不可行”。
为了演示,我创建了一个包含 3 名护士和 5 个空位的护士日程优化程序。
我有两个微不足道的约束:1)第一位护士占据第一个位置,2)每个位置最多允许一名护士。
当一次使用一个约束时,这些约束会导致 or-tools 返回一个可行的解决方案,但是当我同时使用两个约束时,我会得到一个不可行的解决方案。即使使用了两个约束,完全相同的问题在 python API 中也能正常工作。
我怀疑我在AddEquality
设置第一个约束 ( cp_model.AddEquality(LinearExpr(slots[0][0]), 1);
) 时以某种方式滥用,但我无法弄清楚问题是什么。
请帮忙。
#include <iostream>
#include <vector>
#include "ortools/sat/cp_model.h"
#include "ortools/sat/sat_parameters.pb.h"
namespace operations_research {
namespace sat {
void slots(bool add_sum, bool add_const) {
CpModelBuilder cp_model;
const int num_nurses = 3;
const int num_slots = 5;
std::vector<std::vector<IntVar>> slots(num_nurses);
for (int n = 0; n < num_nurses; n++) {
for (int d = 0; d < num_slots; d++) {
const IntVar var = cp_model.NewIntVar({0, 1});
slots[n].push_back(var);
}
}
if (add_const) {
// trival constraint
cp_model.AddEquality(LinearExpr(slots[0][0]), 1);
}
if (add_sum) {
// make the first row sum to one; should be trivial too
std::vector<IntVar> this_nurse_vals(num_nurses);
for (int n = 0; n < num_nurses; n++) {
const IntVar var = slots[n][0];
this_nurse_vals.push_back(var);
}
cp_model.AddEquality(LinearExpr::Sum(this_nurse_vals), 1);
}
// solve
const CpSolverResponse response = Solve(cp_model.Build());
LOG(INFO) << CpSolverResponseStats(response);
for (int d = 0; d < num_slots; d++) {
for (int n = 0; n < num_nurses; n++) {
std::cout << SolutionIntegerValue(response, slots[n][d]);
}
std::cout << std::endl;
}
std::cout << std::endl;
// [END solve]
}
} // namespace sat
} // namespace operations_research
// ----- MAIN -----
int main(int argc, char **argv) {
operations_research::sat::slots(false, true); // works
operations_research::sat::slots(true, false); // works
operations_research::sat::slots(true, true); // infeasible
return EXIT_SUCCESS;
}
// [END program]
在 python 中运行良好的相同程序:
from ortools.sat.python import cp_model
num_nurses = 3
num_slots = 5
model = cp_model.CpModel()
# make vars
slots = {}
for n in range(num_nurses):
for d in range(num_slots):
slots[(n, d)] = model.NewIntVar(0, 1, "slot")
model.Add(slots[(0, 0)] == 1)
model.Add(sum(slots[(n, 0)] for n in range(num_nurses)) == 1)
solver = cp_model.CpSolver()
solver.Solve(model)
solution = []
for d in range(num_slots):
solution.append([])
for n in range(num_nurses):
solution[d].append(solver.Value(slots[(n, d)]))
print(solution)
解决方案
你护士太多了。
这个:
std::vector<IntVar> this_nurse_vals(num_nurses);
创建一个带有num_nurses
元素的向量。
然后你push_back
再添加一个num_nurses
元素,给你你想要的两倍。
从一个空向量开始并push_back
进入它:
std::vector<IntVar> this_nurse_vals;
for (int n = 0; n < num_nurses; n++) {
this_nurse_vals.push_back(IntVar(slots[n][0]));
}
或从“完整”向量开始并分配给它:
std::vector<IntVar> this_nurse_vals(num_nurses);
for (int n = 0; n < num_nurses; n++) {
this_nurse_vals[n] = IntVar(slots[n][0]);
}
推荐阅读
- javascript - 如何防止 Vue v-for 列表中的多次渲染
- java - 如何使用 DateFormat 和 LocalDate 包格式化 ISObasic 日期
- xaml - xaml 设置 RibbonMenuItem 内的边框画笔
- angularjs - 如何在 Angular js 中使用嵌套 json 做 http(ng-repeat)?
- python - 如果我们可以用一个低音类的实例来调用原始的低音类函数,为什么我们有一个超级函数?
- postgresql - 如何在 postgresql 中创建一个在表上创建策略的函数
- javascript - Keycloak:使用 nginx 后面的 javascript 适配器的重定向循环
- python - Django manage.py 命令在 ElasticBeanstalk 上有 SyntaxError
- ssis - 使用putty时执行流程任务参数
- bash - 将 sql-query 的输出复制到文件