主页 / coding / 问题

问题[or-tools](coding)

Martin Hope
RM Ts
Asked: 2024-11-26 23:51:57 +0800 CST
  • 5

我正在尝试在一个项目中使用google CP-SAT 求解器，版本 9.11.4210。问题的一部分包括用另一个变量除以两个变量之和，但求解器返回MODEL_INVALID。我已将问题简化如下：

model = CpModel()
v1 = model.NewIntVar(1, 1, "var1")
v2 = model.NewIntVar(1, 1, "var2")
div = model.NewIntVar(2, 2, "div")
model.add_division_equality(div, v1 + v2, v2)
solver = CpSolver()
status = solver.solve(model)

if status == MODEL_INVALID:
    print("The model is invalid")

当我用 替换分子时，模型并非无效v1 + 1。你知道为什么会发生这种情况或如何解决吗？

or-tools
Martin Hope
Gerard L
Asked: 2024-09-18 17:36:10 +0800 CST
  • 5

从附加的研讨会（带时间戳）中，如果限制所有 presence_literals * interval_size 的总和小于完成时间，则已证明的问题数量会根据视频增加。

当然，我想将其包含在我的基于样本的问题中。但是，我还没有找到如何做到这一点，特别是因为它考虑了机器，所以我的印象是它应该在样本的这一部分中；

 # Transition times and transition costs using a circuit constraint.
  switch_literals = []
  for machine_id in all_machines:
    machine_starts = starts_per_machines[machine_id]
    machine_ends = ends_per_machines[machine_id]
    machine_presences = presences_per_machines[machine_id]
    machine_resources = resources_per_machines[machine_id]
    machine_ranks = ranks_per_machines[machine_id]
    intervals = intervals_per_machines[machine_id]
    arcs = []
    num_machine_tasks = len(machine_starts)
    all_machine_tasks = range(num_machine_tasks)

    for i in all_machine_tasks:
      # Initial arc from the dummy node (0) to a task.
      start_lit = model.NewBoolVar('')
      arcs.append([0, i + 1, start_lit])
      # If this task is the first, set both rank and start to 0.
      model.Add(machine_ranks[i] == 0).OnlyEnforceIf(start_lit)
      model.Add(machine_starts[i] == 0).OnlyEnforceIf(start_lit)
      # Final arc from an arc to the dummy node.
      arcs.append([i + 1, 0, model.NewBoolVar('')])
      # Self arc if the task is not performed.
      arcs.append([i + 1, i + 1, machine_presences[i].Not()])
      model.Add(machine_ranks[i] == -1).OnlyEnforceIf(
          machine_presences[i].Not())

      for j in all_machine_tasks:
        if i == j:
          continue

        lit = model.NewBoolVar('%i follows %i' % (j, i))
        arcs.append([i + 1, j + 1, lit])
        model.AddImplication(lit, machine_presences[i])
        model.AddImplication(lit, machine_presences[j])

        # Maintain rank incrementally.
        model.Add(machine_ranks[j] == machine_ranks[i] + 1).OnlyEnforceIf(lit)

        # Compute the transition time if task j is the successor of task i.
        if machine_resources[i] != machine_resources[j]:
          transition_time = 3
          switch_literals.append(lit)
        else:
          transition_time = 0
        # We add the reified transition to link the literals with the times
        # of the tasks.
        model.Add(machine_starts[j] == machine_ends[i] +
                  transition_time).OnlyEnforceIf(lit)

我尝试按如下方式实现它；

model.Add(sum(machine_presences[i] * intervals[i] for i in all_machine_tasks) <= horizon)

这会产生错误

arg = cmh.assert_is_a_number(arg)

TypeError: Not a number: interval_j5_t11_a0

根据示例，实现此目的的最佳方法是什么？例如，我是否需要duration在机器上为每个任务创建一个变量，然后将该数字与 presence_literal 相乘？我使用 OR-tools 9.8 和 Python。

or-tools
Martin Hope
tobiasBora
Asked: 2024-09-16 22:48:46 +0800 CST
  • 3

我有兴趣使用 MiniZinc，因为它的浏览器内体验和对许多求解器的支持，但同时我发现 CP-SAT（来自 OR-Tools）确实非常高效，并且我想确保通过选择使用 MiniZinc 和 CP-SAT 作为后端，与直接使用 CP-SAT 相比，我不会有任何损失。

所以我的问题是：MiniZinc -> CP-SAT 的转换效率如何？直接在 CP-SAT 中编码有什么好处吗？如果是，我能否以某种方式在 MiniZinc 中提供替代指令，例如一个专门用于 CP-SAT 的指令和一个用于任何通用后端的指令？与 minizinc 的翻译相比，是否有一个已知使用 CP-SAT 更高效的约束列表？

举一个更精确的例子，CP-SAT 有许多函数，如“NoOverlap2D”、“circuits”、“AddReservoirConstraint”……但是否总是存在等效的 MiniZinc 约束，并且它会被正确编译为 CP-SAT？例如，对于 NoOverlap2D，似乎我想使用 diffn，所以如果我使用 diffn，CP-SAT 会在后台使用优化的 NoOverlap2D 代码，还是会从一组可能更难优化的低级指令开始？

另外，在 MiniZinc 挑战赛中，CP-SAT 的性能是通过用 MiniZinc 编写的代码获得的，还是直接通过针对 CP-SAT 优化的代码获得的？

or-tools