线性规划-绝对值大于常数

Question

如何转换约束|x|>=2，使其在线性程序中工作（特别是使用单纯形求解）。

我了解如何转换|x|<=2，因为这将变成x<=2和-x<=2

然而，当你有一个最小常数时，同样的逻辑就不起作用了。

Answer 1

没有办法将像|x|>=2这样的方程硬塞进纯（连续）LP中。你需要公式化x <= -2 OR x >= 2，它是非凸的。这将需要一个二进制变量，使问题成为MIP。

一种配方可以是：

x >= 2 - delta*M
x <= -2 + (1-delta)*M
delta in {0,1}

其中CCD_ 3被明智地选择为大的数字。例如，如果是-100<=x<=100，则可以选择M=102。