constraints - 在线性规划中表达 OR 约束

Question

我有一个浮点变量 x在一个线性程序中，它应该是 0或两个常量之间 CONSTANT_A和 CONSTANT_B :

LP.addConstraint(x == 0 OR CONSTANT_A <= x <= CONSTANT_B)

当然没有明确的OR这样的东西在线性规划中。有没有办法表达这种约束？

Answer 1

那么让我们假设您想要约束:

x == 0 OR 1 <= x <= 2

很明显，你的线性规划的可行域不是凸的，因为 x=0 和 x=1 都是可行的，但没有适当的凸组合是可行的。因此，证明不可能用线性程序对此进行建模。

话虽这么说，但如果您引入二元决策变量 y，则很容易对此建模，如果我们在范围内，则取值 1，如果我们固定为 0，则取值 0。然后您可以建模如下:

y <= x <= 2*y
y binary

或者，在您完全一般的情况下:

y*CONSTANT_A <= x <= y*CONSTANT_B
y binary