线性规划约束“x >= c 或 x = 0”

Question

我想表达一个线性程序，其变量只能大于或等于常数 c 或等于 0。范围 ]0; c[ 是不允许的。

您是否知道一种在线性程序中表达此约束的方法，并且可以使用未经修改的单纯形实现来解决该约束？

例如此约束：x1 >= 4 或 x1 = 0。

线性程序中所有约束之间的典型关系是 AND。这是两个约束之间的或。

注意：我需要以计算有效的方式解决具有多个变量的问题。

Answer 1

具有您定义的约束的数学程序无法表示为线性程序，因此无法使用未经修改的单纯形实现来求解。推理很简单——线性规划的可行集必须是凸的。像这样的集合{x = 0 or x >= 2}不是凸的，因为它包含点x=0和x=2但不包含x=1。

因此，您将被迫使用其他数学编程技术；我想到的是混合整数线性规划（MILP）。x_i对于具有以下形式约束的每个变量，x_i = 0 or x_i >= c_i您将定义 辅助变量y_i以及以下约束：

x_i >= c_iy_i
x_i <= My_i
y_i binary

如果y_i=0，那么约束就是x_i >= 0; x_i <= 0，意思x_i=0。如果y_i=1，那么约束条件是x_i >= c_i, x_i <= M。您应该M为您的问题设置一个足够大的值，但要小心不要设置M太大，因为这将使您的问题更难解决。

这在计算上是否易于处理取决于数学程序的大小和结构以及您使用的求解器的质量。MILP 求解器有多种选择；例如，在 R 中，您可以使用lpSolve、lpSolveAPI或Rglpk库，或者在 MATLAB 中您可以使用该intlinprog函数。一般来说，cplex 和 gurobi 被认为是最好的 MILP 求解器，但两者都是商业的，并且需要许可证。