mathematical-optimization - 线性规划约束 "x >= c or x = 0"

Question

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

您是否知道在线性规划中表达此约束的方法，并且可以使用未修改的单纯形实现来求解？

例如这个约束:x1 >= 4 或 x1 = 0。

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

注意:我需要以计算效率高的方式解决具有多个此类变量的问题。

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 求解器，但两者都是商业的，需要许可证。