具有逻辑与运算的混合整数编程 IF-THEN
Mixed Integer Programming IF-THEN with Logical AND operation
我有以下约束，我正在尝试使用 Python 的 PuLP 模块在混合整数编程中建模：
给定线性规划变量：x1,x2,y1,y2 其中 x1、x2、y1、y2 最终求解为整数值
if (x1<=y2 and y1<=x2) then a=1 else b=0
我不确定如何处理 IF condition 中的 Logical AND。如果 AND 不存在，我知道我必须使用 Big-M 表示法。
首先，这不是线性规划而是混合整数规划，因为AND约束不是线性的，也不是蕴涵的。我还假设 a 和 b 都是二进制变量。然后您可以按如下方式重新表述您的问题：
x1 > y2 + m*z1
y1 > x2 + m*z2
a + 1 >= z1 + z2
a <= z1
a <= z2
a - b >= 0
这里，m 需要是某个（负）下限，即 m < x1-y2 和 m < y1-x2。 z1 和 z2 都是二进制变量。要绕过 < 不等式，您可能需要在前两个约束中添加一些小的 epsilon：
x1 >= y2 + (m-eps)*z1 + eps
y1 >= x2 + (m-eps)*z2 + eps
我找到了一个公式，无论给定的问题如何，都可以 IF-THEN-ELSE 起作用。
在答案的后半部分，我使用@mattmilten 的答案中描述的 z1, z2 变量来处理 if statement
中的 AND condition
假设问题是以下规范：
if α > 0 then β >= 0 else γ >= 0
然后，
α - z * U_α <= 0 # (1)
α - (1 - z)(L_α - 1) > 0 # (2)
β - (1 - z)L_β >= 0 # (3)
γ - z * L_γ >= 0 # (4)
其中，
L_α, L_β, L_γ # are constant lower bounds on α, β, γ (or values smaller than the lowest value they can take)
U_α # is a constant lower bounds on α
z # is a LP variable that can take values {0,1}
如果 z==1
那么等式(1)和(4)是多余的，then condition或(3)被强制执行
如果 z==0
则等式(2)、(3)是多余的，强制执行else condition或(4)
对于这个问题
我们运行这两次，第一次α=α1，第二次α=α2。
其中，
α1 = y2 - x1
z1 = decision variable for α1 with values {0,1}
α2 = y1 - x2
z2 = decision variable for α2 with values {0,1}
β # Currently unnecessary for my particular question.
γ # Currently unnecessary for my particular question.
所以我们的约束变成：
α1 - z1 * U_α1 <= 0 # (1-1)
α1 - (1 - z1)(L_α1 - 1) > 0 # (1-2)
α2 - z2 * U_α2 <= 0 # (2-1)
α2 - (1 - z2)(L_α2 - 1) > 0 # (2-2)
如果 z1=1，那么我们的 if-condition 的第一部分为真。 IE。 x1<=y2
如果z2=1，那么我们if-condition的第二部分为真。 IE。 x2<=y1
现在，使用@mattmilten 的公式来确保这两个条件：
a + 1 >= z1 + z2
a <= z1
a <= z2
a - b >= 0
这确保 z1 和 z2 都必须 >= 1 才能使 a=1。如果 a=1 那么 b 可以是 b=1 或 b=0 而不违反最后一个条件。
如果 a=0 那么我们处于 else 条件，因此 b 必须为 0。
我有以下约束，我正在尝试使用 Python 的 PuLP 模块在混合整数编程中建模：
给定线性规划变量：x1,x2,y1,y2 其中 x1、x2、y1、y2 最终求解为整数值
if (x1<=y2 and y1<=x2) then a=1 else b=0
我不确定如何处理 IF condition 中的 Logical AND。如果 AND 不存在，我知道我必须使用 Big-M 表示法。
首先，这不是线性规划而是混合整数规划，因为AND约束不是线性的，也不是蕴涵的。我还假设 a 和 b 都是二进制变量。然后您可以按如下方式重新表述您的问题：
x1 > y2 + m*z1
y1 > x2 + m*z2
a + 1 >= z1 + z2
a <= z1
a <= z2
a - b >= 0
这里，m 需要是某个（负）下限，即 m < x1-y2 和 m < y1-x2。 z1 和 z2 都是二进制变量。要绕过 < 不等式，您可能需要在前两个约束中添加一些小的 epsilon：
x1 >= y2 + (m-eps)*z1 + eps
y1 >= x2 + (m-eps)*z2 + eps
我找到了一个公式，无论给定的问题如何，都可以 IF-THEN-ELSE 起作用。
在答案的后半部分，我使用@mattmilten 的答案中描述的 z1, z2 变量来处理 if statement
AND condition
假设问题是以下规范：
if α > 0 then β >= 0 else γ >= 0
然后，
α - z * U_α <= 0 # (1)
α - (1 - z)(L_α - 1) > 0 # (2)
β - (1 - z)L_β >= 0 # (3)
γ - z * L_γ >= 0 # (4)
其中，
L_α, L_β, L_γ # are constant lower bounds on α, β, γ (or values smaller than the lowest value they can take)
U_α # is a constant lower bounds on α
z # is a LP variable that can take values {0,1}
如果 z==1
那么等式(1)和(4)是多余的，then condition或(3)被强制执行
如果 z==0
则等式(2)、(3)是多余的，强制执行else condition或(4)
对于这个问题
我们运行这两次，第一次α=α1，第二次α=α2。
其中，
α1 = y2 - x1
z1 = decision variable for α1 with values {0,1}
α2 = y1 - x2
z2 = decision variable for α2 with values {0,1}
β # Currently unnecessary for my particular question.
γ # Currently unnecessary for my particular question.
所以我们的约束变成：
α1 - z1 * U_α1 <= 0 # (1-1)
α1 - (1 - z1)(L_α1 - 1) > 0 # (1-2)
α2 - z2 * U_α2 <= 0 # (2-1)
α2 - (1 - z2)(L_α2 - 1) > 0 # (2-2)
如果 z1=1，那么我们的 if-condition 的第一部分为真。 IE。 x1<=y2
如果z2=1，那么我们if-condition的第二部分为真。 IE。 x2<=y1
现在，使用@mattmilten 的公式来确保这两个条件：
a + 1 >= z1 + z2
a <= z1
a <= z2
a - b >= 0
这确保 z1 和 z2 都必须 >= 1 才能使 a=1。如果 a=1 那么 b 可以是 b=1 或 b=0 而不违反最后一个条件。
如果 a=0 那么我们处于 else 条件，因此 b 必须为 0。