If-Then-ElseIf-Then 在混合整数线性规划中
If-Then-ElseIf-Then In Mixed Integer Linear Programming
我正在尝试在 Python 的 PuLP 中构建 If-Then-Else-If... 条件。
我查看了 MIP 中的 If-Then
和 If-Then-Else
。
但是,我试图了解如何将选择进一步向下传播到下一组约束以及如何处理 2 个以上的决策分支。
为了解释,请考虑 image shown here 中显示的条件约束:
x 和 y 是我的决策变量。
基本上,这读作:
if x=0: C2>0
elif x=1: C10>0
elif x=2: C3>0
if x=0 and y=0:
C4>0;
C8>0;
C10>0
elif x=0 and y=1:
C5>0;
C8>0;
C10>0
elif x=2 and y=0:
C6>0;
C9>0;
C10>0
elif x=2 and y=1:
C7>0;
C9>0;
C10>0
我知道如何在简单的 if-then-else 情况下使用 "Big M" 技术。例如,如果问题是:
Problem:
if (x = 1) then (A < 0) else (B < 0)
Solution:
problem += A < M1*(1-x)
problem += B < M2*x
我不明白的是,如何将其更改为:
- 如果超过2个分支,则不再是x和(1-x)的乘法。
- 如果原始决策下方有后续分支,更多决策都取决于上面的值。
这里实际上涉及三个步骤:
第一个:
重新表述 x
变量,使它们成为二进制而不是 {0,1,2}。 (严格来说,这不是必需的,但我认为它使解决方案更清晰,更容易概括。)
所以,引入三个新的二元变量x0
、x1
、x2
并约束如下:
x0 >= 1 - x
x0 <= 1 - 0.5x
x2 >= x - 1
x2 <= 0.5 x
x1 = x - 2x2
因此:如果 x = 0
,则前两个约束需要 x0 = 1
,后两个需要 x2 = 0
,最后一个需要 x1 = 0
。同样,如果 x = 1
或 x = 2
。 (你应该仔细检查我的逻辑。)
您的模型将包括原始 x
变量和新的二元变量。
第二个:
创建一个名为 w_ijkl
的新二元决策变量,如果 x0 = i
、x1 = j
、x2 = k
和 y = l
,它等于 1,因为{0,1} 中的 i
、j
、k
、l
。通过以下约束强制执行此定义:
w_ijkl >= i*x0 + (1-i)*(1-x0) + j*x1 + (1-j)*(1-x1) +
k*x2 + (1-k)*(1-x2) + l*y + (1-l)*(1-y) - 3
w_ijkl <= 0.25 * [i*x0 + (1-i)*(1-x0) + j*x1 + (1-j)*(1-x1) +
k*x2 + (1-k)*(1-x2) + l*y + (1-l)*(1-y)]
第一个约束表示如果所有四个变量都等于它们的目标(i
、j
等),那么 w_ijkl
必须等于 1,否则它可以等于 0。第二个约束说如果所有四个都等于他们的目标,那么 w_ijkl
可能等于 1,否则它必须等于 0.
因此,例如,w_0110 获得这些约束:
w_0110 >= 1-x0 + x1 + x2 + (1-y) - 3
w_0110 <= 0.25 * [1-x0 + x1 + x2 + (1-y)]
第三名:
根据需要使用 big-M
s 来打开和关闭约束。因此,例如,如果 x=2
和 y=0
需要 C6 >= 0
,请使用:
C6 >= M * (w_0010 - 1)
(顺便说一下,通常您不能在 MIP 中使用严格的不等式约束——您需要大于或等于或小于或等于约束。)
我正在尝试在 Python 的 PuLP 中构建 If-Then-Else-If... 条件。
我查看了 MIP 中的 If-Then
和 If-Then-Else
。
但是,我试图了解如何将选择进一步向下传播到下一组约束以及如何处理 2 个以上的决策分支。
为了解释,请考虑 image shown here 中显示的条件约束:
x 和 y 是我的决策变量。 基本上,这读作:
if x=0: C2>0
elif x=1: C10>0
elif x=2: C3>0
if x=0 and y=0:
C4>0;
C8>0;
C10>0
elif x=0 and y=1:
C5>0;
C8>0;
C10>0
elif x=2 and y=0:
C6>0;
C9>0;
C10>0
elif x=2 and y=1:
C7>0;
C9>0;
C10>0
我知道如何在简单的 if-then-else 情况下使用 "Big M" 技术。例如,如果问题是:
Problem:
if (x = 1) then (A < 0) else (B < 0)
Solution:
problem += A < M1*(1-x)
problem += B < M2*x
我不明白的是,如何将其更改为:
- 如果超过2个分支,则不再是x和(1-x)的乘法。
- 如果原始决策下方有后续分支,更多决策都取决于上面的值。
这里实际上涉及三个步骤:
第一个:
重新表述 x
变量,使它们成为二进制而不是 {0,1,2}。 (严格来说,这不是必需的,但我认为它使解决方案更清晰,更容易概括。)
所以,引入三个新的二元变量x0
、x1
、x2
并约束如下:
x0 >= 1 - x
x0 <= 1 - 0.5x
x2 >= x - 1
x2 <= 0.5 x
x1 = x - 2x2
因此:如果 x = 0
,则前两个约束需要 x0 = 1
,后两个需要 x2 = 0
,最后一个需要 x1 = 0
。同样,如果 x = 1
或 x = 2
。 (你应该仔细检查我的逻辑。)
您的模型将包括原始 x
变量和新的二元变量。
第二个:
创建一个名为 w_ijkl
的新二元决策变量,如果 x0 = i
、x1 = j
、x2 = k
和 y = l
,它等于 1,因为{0,1} 中的 i
、j
、k
、l
。通过以下约束强制执行此定义:
w_ijkl >= i*x0 + (1-i)*(1-x0) + j*x1 + (1-j)*(1-x1) +
k*x2 + (1-k)*(1-x2) + l*y + (1-l)*(1-y) - 3
w_ijkl <= 0.25 * [i*x0 + (1-i)*(1-x0) + j*x1 + (1-j)*(1-x1) +
k*x2 + (1-k)*(1-x2) + l*y + (1-l)*(1-y)]
第一个约束表示如果所有四个变量都等于它们的目标(i
、j
等),那么 w_ijkl
必须等于 1,否则它可以等于 0。第二个约束说如果所有四个都等于他们的目标,那么 w_ijkl
可能等于 1,否则它必须等于 0.
因此,例如,w_0110 获得这些约束:
w_0110 >= 1-x0 + x1 + x2 + (1-y) - 3
w_0110 <= 0.25 * [1-x0 + x1 + x2 + (1-y)]
第三名:
根据需要使用 big-M
s 来打开和关闭约束。因此,例如,如果 x=2
和 y=0
需要 C6 >= 0
,请使用:
C6 >= M * (w_0010 - 1)
(顺便说一下,通常您不能在 MIP 中使用严格的不等式约束——您需要大于或等于或小于或等于约束。)