And/Or 约束的混合整数线性规划

Question

我希望使用 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。

如有任何帮助，我们将不胜感激。谢谢！

Answer 1

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

现在让我们假设您的任务如下所示：((x1<=x2) && (x1<=x3)) || ((x1>x2) && (x1>x3))（> 是此处 <= 的逻辑否定，尽管有上述情况，它仍能正常工作）。

让我们调用 (x1>x2) = z1 和 (x1>x3) = z2。那么这可以是 simplified 到： (!z1 || z2) && (z1 || !z2) （我在 link 中使用了名称 A 和 B）。

引入两个新的二进制变量z1, z2
使用基于 bigM 的公式 like this page 4 为您的关系创建一个指标：
- 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)（看上面"simplified"link中的真相-table）你可以跟着一个非常活跃的 Whosebug 用户 here 来线性化 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

（上面可能有些错误，但概念应该没问题，手头有代码应该可以实现）

Answer 2

约束条件

 ((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}

Mixed Integer Linear Programming to And/Or Constraints