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

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}

其中M明智地选择了大量。例如如果-100<=x<=100那么你可以选择M=102。