python - 使用逻辑与运算的混合整数编程 IF-THEN

Question

我有以下约束，我试图用 Python 的 PuLP 模块在混合整数编程中建模：

给定线性规划变量：x1,x2,y1,y2其中 x1, x2, y1, y2 最终求解为整数值

if (x1<=y2 and y1<=x2) then a=1 else b=0

我不确定如何处理Logical AND. IF condition如果AND不存在，我知道我必须使用 Big-M 符号。

Answer 1

首先，这不是线性规划而是混合整数规划，因为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

Answer 2

我找到了一个IF-THEN-ELSE不管给出的问题如何都有效的公式。在答案的后半部分，我使用z1, z2@mattmilten 的答案中描述的变量来AND condition处理if statement

假设问题是以下规范：

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 conditionor (3) 被强制执行

如果 z==0

那么等式 (2) 和 (3) 是多余的，并且else conditionor (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 条件的第一部分为真。IE。x1<=y2

如果 z2=1，那么我们的 if 条件的第二部分为真。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。