在线性规划中将条件约束转换为线性约束 [英] Converting conditional constraints to linear constraints in Linear Programming

问题描述

我有两个变量:x> = 0和y二进制(0或1)，并且我有一个常数z> =0.如何使用线性约束来描述以下条件:

I have two variables: x>= 0 and y binary (either 0 or 1), and I have a constant z >= 0. How can I use linear constraints to describe the following condition:

If x = z then y = 1 else y = 0.

我试图通过定义另一个二进制变量i和一个足够大的正常数U并添加约束来解决此问题

I tried to solve this problem by defining another binary variable i and a large-enough positive constant U and adding constraints

y - U * i = 0;
x - U * (1 - i) = z;

这正确吗?

推荐答案

您要询问的约束确实有两类:

Really there are two classes of constraints that you are asking about:

1. 如果为y=1，则为x=z.对于某些较大的常量M，您可以添加以下两个约束以实现此目的:

1. If y=1, then x=z. For some large constant M, you could add the following two constraints to achieve this:

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值.

If y=1 then these constraints are equivalent to x-z <= 0 and z-x <= 0, meaning x=z, and if y=0, then these constraints are x-z <= M and z-x <= M, which should not be binding if we selected a sufficiently large M value.

1. 如果y=0，则x != z.从技术上讲，您可以通过添加另一个控制x > z(q=1)或x < z(q=0)的二进制变量q来实施此约束.然后，您可以添加以下约束，其中m是一些小的正值，而M是一些大的正值:

1. If y=0 then x != z. Technically you could enforce this constraint by adding another binary variable q that controls whether x > z (q=1) or x < z (q=0). Then you could add the following constraints, where m is some small positive value and M is some large positive value:

x-z >= mq - M(1-q)
x-z <= Mq - m(1-q)

如果q=1，则这些约束将x-z绑定到范围[m, M]，如果q=0，则这些约束将x-z绑定到范围[-M, -m].

If q=1 then these constraints bound x-z to the range [m, M], and if q=0 then these constraints bound x-z to the range [-M, -m].

在实践中，使用求解器时，通常不会真正确保x != z，因为通常允许较小的范围冲突.因此，建议不要使用任何约束来强制执行此规则，而不要使用这些约束.然后，如果使用y=0和x=z获得最终解决方案，则可以将x调整为采用x+epsilon或x-epsilon的值，以获得epsilon的一些极小的值.

In practice when using a solver this usually will not actually ensure x != z, because small bounds violations are typically allowed. Therefore, instead of using these constraints I would suggest not adding any constraints to your model to enforce this rule. Then, if you get a final solution with y=0 and x=z, you could adjust x to take value x+epsilon or x-epsilon for some infinitesimally small value of epsilon.

这篇关于在线性规划中将条件约束转换为线性约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！