linear-programming - 将条件约束转换为线性规划的线性约束

Question

我有两个变量：C 是二进制的，X 是非负的

如果 C = 0，则 X = 0；如果 C = 1 则 X = X（意味着对 X 没有约束）

我应该如何将此条件约束格式化为 LP 的线性约束？

标签： linear-programming

Answer 1

请注意，严格来说 LP 模型仅包含连续变量。所以我们假设这是一个用 MIP 求解器求解的 MIP 模型。

以下是解决此问题的三种方法，具体取决于求解器的能力。

(1) 如果您使用支持指标约束的求解器，您可以简单地使用：

 c=0 ==> x=0

(2) 对于其他求解器，您可以使用：

 x <= M*c

其中 M 是 x 的（尽可能紧的）上界。

(3) 最后，如果你的求解器支持 SOS1 (Special Ordered Sets of type 1) 集，你可以使用：

 d = 1-c
 {d,x} ∈ SOS1
 d >= 0

(1) 和 (3) 的优点是不需要界限。如果你对 x 有一个好的、严格的界限，那么 (2) 是一个不错的选择。