CP-SAT 中的 OR 约束

Question

我们有什么方法可以使用 CP-SAT 类方法对以下示例公式进行编程：

(x + y >=10) V (x - y <= 5) V (y >= 2 )

我知道 M 方法的大技巧，但我无法使用 CP-SAT 功能。

Boolean

变量对我有帮助吗？

任何人都可以给我一个简短的程序以便我能明白这个想法吗？

Answer 1

取决于求解器。我假设您正在谈论来自 Google 的 OR 工具的 CP-SAT。您可以使用二元变量和

OnlyEnforceIf

来实现以下数学模型：

b1=1 => x+y>=10
b2=1 => x-y<=5
b3=1 => y>=2
b1+b2+b3 >= 1
b1,b2,b3 ∈ {0,1}

第一个含义可以是这样的：

  model.Add(x+y>=10).OnlyEnforceIf(b1)

其他人也类似。总和可以按原样表示，也可以表示为：

  model.AddBoolOr(b1, b2, b3)

（我更喜欢求和，但那是因为我习惯了 MIP 模型）。我希望他们能解决同样的问题。

请注意，许多 MIP 求解器也可以进行暗示（它们被称为指标约束）。如果没有，您可能需要使用 big-M 约束（书呆子：或 SOS1 集）。

根据含义（而不是“如果”）来思考通常很有用。它们很容易被人类读者和（大多数）求解者理解。