在线性规划中将条件约束转换为线性约束
Converting conditional constraints to linear constraints in Linear Programming
我有两个变量：x>= 0 和 y 二进制（0 或 1），我有一个常量 z >= 0。如何使用线性约束来描述以下条件：
If x = z then y = 1 else y = 0.
我试图通过定义另一个二进制变量 i 和一个足够大的正常数 U 并添加约束来解决这个问题
y - U * i = 0;
x - U * (1 - i) = z;
这是正确的吗？
确实有两个 类 您要问的限制条件：
- 如果
y=1，则x=z。对于一些大常量 M，您可以添加以下两个约束来实现此目的：
x-z <= M*(1-y)
z-x <= M*(1-y)
如果y=1那么这些约束等价于x-z <= 0和z-x <= 0，意思是x=z，如果y=0，那么这些约束就是x-z <= M 和 z-x <= M，如果我们选择了足够大的 M 值，则它们不应具有约束力。
- 如果
y=0 则 x != z。从技术上讲，您可以通过添加另一个控制 x > z (q=1) 或 x < z (q=0) 的二进制变量 q 来强制执行此约束。然后你可以添加以下约束，其中 m 是一些小的正值，M 是一些大的正值：
x-z >= mq - M(1-q)
x-z <= Mq - m(1-q)
如果 q=1 则这些约束将 x-z 绑定到范围 [m, M]，如果 q=0 则这些约束将 x-z 绑定到范围 [-M, -m].
在实践中，当使用求解器时，这通常不会真正确保 x != z，因为通常允许小范围违规。因此，我建议不要向您的模型添加任何约束来强制执行此规则，而不是使用这些约束。然后，如果你得到 y=0 和 x=z 的最终解决方案，你可以调整 x 取值 x+epsilon 或 x-epsilon 的一些无限小的值 epsilon.
所以我将条件约束更改为
if x = z then y = 0 else y = 1
那么答案就是
x - z <= M * y;
x - z >= m * y;
其中M是一个足够大的正数，m是一个足够小的正数。
我有两个变量：x>= 0 和 y 二进制（0 或 1），我有一个常量 z >= 0。如何使用线性约束来描述以下条件：
If x = z then y = 1 else y = 0.
我试图通过定义另一个二进制变量 i 和一个足够大的正常数 U 并添加约束来解决这个问题
y - U * i = 0;
x - U * (1 - i) = z;
这是正确的吗？
确实有两个 类 您要问的限制条件：
- 如果
y=1，则x=z。对于一些大常量M，您可以添加以下两个约束来实现此目的：
x-z <= M*(1-y)
z-x <= M*(1-y)
如果y=1那么这些约束等价于x-z <= 0和z-x <= 0，意思是x=z，如果y=0，那么这些约束就是x-z <= M 和 z-x <= M，如果我们选择了足够大的 M 值，则它们不应具有约束力。
- 如果
y=0则x != z。从技术上讲，您可以通过添加另一个控制x > z(q=1) 或x < z(q=0) 的二进制变量q来强制执行此约束。然后你可以添加以下约束，其中m是一些小的正值，M是一些大的正值：
x-z >= mq - M(1-q)
x-z <= Mq - m(1-q)
如果 q=1 则这些约束将 x-z 绑定到范围 [m, M]，如果 q=0 则这些约束将 x-z 绑定到范围 [-M, -m].
在实践中，当使用求解器时，这通常不会真正确保 x != z，因为通常允许小范围违规。因此，我建议不要向您的模型添加任何约束来强制执行此规则，而不是使用这些约束。然后，如果你得到 y=0 和 x=z 的最终解决方案，你可以调整 x 取值 x+epsilon 或 x-epsilon 的一些无限小的值 epsilon.
所以我将条件约束更改为
if x = z then y = 0 else y = 1
那么答案就是
x - z <= M * y;
x - z >= m * y;
其中M是一个足够大的正数，m是一个足够小的正数。