or-tools：简单的问题在 cpp 中不可行，但在 python 中有效

Question

我运行遇到了优化问题中的一个问题，在该问题中，平凡可行的约束导致我的 cpp 程序在尝试求解时 return "infeasible"。

为了演示，我创建了一个包含 3 个护士和 5 个槽位的护士排班优化程序。

我有两个微不足道的限制：1) 第一个护士占据第一个位置，2) 每个位置最多允许一名护士。

当一次使用一个约束时，这些约束会导致 or-tools return 一个可行的解决方案，但是当我同时使用两个约束时，我会得到一个不可行的解决方案。完全相同的问题在 python API 中运行良好，即使同时使用两个约束。

我怀疑我在设置第一个约束 (cp_model.AddEquality(LinearExpr(slots[0][0]), 1);) 时以某种方式误用了 AddEquality，但我无法弄清楚问题出在哪里。

请帮忙

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

Answer 1

你的护士太多了。

这个：

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]));
}

或者从一个"full"向量开始并赋值给它：

std::vector<IntVar> this_nurse_vals(num_nurses);
for (int n = 0; n < num_nurses; n++) {
    this_nurse_vals[n] = IntVar(slots[n][0]);
}

or-tools：简单的问题在 cpp 中不可行，但在 python 中有效

or-tools: Trivial problem is infeasible in cpp, but works in python

c++

python

or-tools