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

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。