1

我希望使用 PuLP 来满足一组约束，但我不确定如何设置变量来做到这一点。

例如，我将如何为以下约束设置变量：

((x_1 < x_2) AND (x_1 < x_3)) OR ((x_1 > x_2) AND (x_1 > x_3))

变量 x_1 要么小于要么大于 x_2 和 x_3。

任何帮助，将不胜感激。谢谢！

4

2 回答 2

4

约束

 ((x1 <= x2) AND (x1 <= x3)) OR ((x1 >= x2) AND (x1 >= x3))

可以只用一个额外的二进制变量来表示：

 x1 <= x2 + delta*M
 x1 <= x3 + delta*M
 x1 >= x2 - (1-delta)*M
 x1 >= x3 - (1-delta)*M
 delta in {0,1}

大多数高级求解器都有指标约束，允许我们在没有大 M 的情况下编写：

 delta = 0 -> x1 <= x2
 delta = 0 -> x1 <= x3
 delta = 1 -> x1 >= x2
 delta = 1 -> x1 >= x3
 delta in {0,1}
于 2017-11-26T04:36:34.620 回答
2

<首先说明：线性规划中没有运算符。只有<=. 这意味着：如果你想要严格的不等式，你需要添加一些小的常数epsilon！

现在让我们假设您的任务看起来像：（((x1<=x2) && (x1<=x3)) || ((x1>x2) && (x1>x3))是>这里的逻辑否定，<=尽管有上述情况，这仍将使这项工作）。

让我们调用(x1>x2) = z1和(x1>x3) = z2。然后可以将其简化为：（(!z1 || z2) && (z1 || !z2)我在链接中使用了名称 A 和 B）。

  • 引入两个新的二元变量z1, z2
  • 使用第 4 页这样的基于 bigM 的公式为您的关系创建指标：
    • x1 <= x2 + M * z1其中 M 是一个大常数；(z1=0) -> x1 <= x2
    • x1 <= x3 + M * z2其中 M 是另一个大常数；(z2=0) -> x1 <= x3
  • 现在我们需要上面的：(!z1 || z2) && (z1 || !z2)
    • 这基本上是一个!(z1 xor z2)，在这里1-(z1 xor z2)（查看上面“简化”链接中的真值表），您可以在此处关注一个非常活跃的 Stackoverflow 用户来线性化xor：
      • 引入另一个二进制变量z3
      • 添加线性约束
        • z3 <= (1-z1) + (1-z2)
        • z3 >= (1-z1) - (1-z2)
        • z3 >= (1-z2) - (1-z1)
        • z3 <= 2 - (1-z1) - (1-z2)
    • z3就是现在z1 xor z2
    • 添加约束：z3 == 0

（上面可能有一些错误，但这个概念应该没问题。有了手头的代码，你应该可以让它工作）

于 2017-11-25T22:55:53.683 回答