如果-那么-否则如果-那么 在混合整数线性规划中

Question

我正在尝试在Python的PuLP中构建If-Then-Else-If条件语句。我已经查看了MIP中的If-Then和If-Then-Else。但是，我想了解如何将选择向下传播到下一组约束，并处理超过2个决策分支的情况。为了说明，考虑此处所示的条件约束：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

我可以使用“大M法”解决简单的if-then-else情况。例如，如果问题是：

Problem: 
   if (x = 1) then (A < 0) else (B < 0)
Solution: 
   problem += A < M1*(1-x)
   problem += B < M2*x

我不明白的是如何将以下内容改为：

1. 如果有超过2个分支，那么它不再是x和（1-x）的乘法。
2. 如果在原始决策下方有后续分支，其中包含更多的决策，所有这些决策都依赖于上面的值。

请注意保留HTML标记。

- SashaZd

Answer 1

这里实际上涉及到三个步骤：

第一步：

重新定义变量 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（其中 i、j、k、l 属于 {0,1}），则等于 1。通过以下约束条件强制执行此定义：

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)]

第三步：

根据需要使用大写M来开启或关闭限制条件。例如，如果要求在x=2且y=0时C6 >= 0，则使用以下代码：

C6 >= M * (w_0010 - 1)

（顺便说一下，在整数规划中通常不能使用严格不等式约束条件——需要使用大于等于或小于等于的约束条件。）

- LarrySnyder610