python - 有什么方法可以使用 Google OR Tools for python 设置析取约束吗？

Question

我正在尝试使用 Google OR 为 Python 3.7 构建整数 LP 模型。而且我不知道如何创建析取约束。假设，有 {x1, x2, x3, x4, x5, ...} 变量，我想将几​​个条件分离为一个，有点像:x1 + x2 = 2 | x2 + x3 = 2 | x3 + x4 = 2因此，要满足该条件 x2 + x3 = 2 就足够了。

据我了解，这是可能的并且称为析取条件。对于 OR 工具，我找到了 some explanation ，但它适用于 C++，看起来已经过时了。还有tutorial by google ，但它是用于 CP，而不是 LP 任务，所以我不知道如何在我的案例中使用它(我没有建模，只有求解器)

我的任务是确定轮类期间的晚餐时间(假设为 2 小时)，尽可能减少重叠。对于变量 0 代表晚餐时间，1 代表工作时间。所以，这是我现在得到的一些简化版本:

...
solver = pywraplp.Solver('SolveIntegerProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
objective = solver.Objective()

for e in employees:
  for d in days:
    # setting up a constraint that during workday employee should have a dinner time for 2 hours
    dinner_constraint = solver.Constraint(-solver.infinity(), e.end_hour - e.start_hour - 1) # force to spend at least 2 hours for dinner
    for h in range(e.start_hour, e.end_hour):
      variables[(e, d, h)] = solver.IntVar(0.0, 1.0, 'mhr_{}_{}_{}'.format(e, d, h))
      objective.SetCoefficient(variables[(e, d, h)], 1)
      dinner_constraint.SetCoefficient(variables[(e, d, h)], 1)
    for h in range(e.start_hour, e.end_hour - 1): # e.end_hour - 1 due to dinner is 2 hours
      dinner_sub_constraint = solver.Constraint(2)
      dinner_sub_constraint.SetCoefficient(variables[(e, d, h)], 1)
      dinner_sub_constraint.SetCoefficient(variables[(e, d, h + 1)], 1)
      # here I want to disjunct dinner_sub_constraint for each iteration in one constraint
objective.SetMaximization()
result_status = solver.Solve()
...

所以，我只想分离所有的 dinner_sub_constraint 并将其设置为单个约束。

这可能是一种奇怪的方法，但我不知道如何连续提供两个小时的晚餐，所以在一个类次中有两个 1 小时的晚餐是 Not Acceptable 。有什么办法可以分离条件吗？还是我的做法不对？或者我应该使用另一个库？

Answer 1

您应该使用 CP-SAT 求解器。在 examples/python 中查找 shift_scheduling_sat.py。