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

Question

你将如何转换约束 |x| >= 2，以便它可以在线性程序中工作（特别是使用 Simplex 求解）。

我了解如何转换 |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.