PuLP中互斥变量约束下出现不可行状态的解决问询

问题背景 #

使用PuLP求解优化问题时，设置决策变量总和≤50并施加互斥约束后，持续得到Status: Infeasible结果。具体问题：

• 通过二进制变量y1/y2/y3约束P1/P2/P3互斥，y4/y5约束P4/P5互斥，但PuLP仅约束了y变量的互斥性，未限制未选中的P变量——所有P变量仍取下限值，导致总和远超50。
• 期望实现的约束为非线性形式P1*y1 + P2*y2 + P3*y3 + P4*y4 + P5*y5 <= 50，但PuLP不支持非线性约束，直接添加会报错。

错误原因 #

原代码中的P变量约束逻辑错误：

• 原约束P1 <= y1*大M +10仅限制了P1的上限，但P1的下限是10，当y1=0时，P1仍会取下限10，未被强制置0。
• 总和约束P1+P2+P3+P4+P5 <=50包含了所有未选中P变量的下限值（10+20+30+15+30=105），远大于50，导致问题不可行。

解决方案：线性化非线性约束 #

通过大M法将非线性约束转化为线性约束，核心思路是：

• 当二进制变量y_i=1（选中对应P变量）时，P变量在其原上下限范围内取值；
• 当y_i=0（未选中）时，强制P变量为0，避免其计入总和。

具体约束调整：

1. 将所有P变量的下限改为0；
2. 添加以下线性约束：
   • P_i <= 上限_i * y_i：确保未选中时P_i=0，选中时不超过原上限；
   • P_i >= 下限_i * y_i：确保选中时P_i不低于原下限，未选中时P_i≥0（结合上一约束，P_i=0）；
3. 总和约束保持P1+P2+P3+P4+P5 <=50即可，此时等价于期望的非线性约束。

修改后的代码 #

from pulp import *

# 定义最大化问题
prob = LpProblem("AVB-Problem", LpMaximize)

# 定义决策变量：P变量下限改为0，保留原上限
P1 = LpVariable("P1", 0, 20)
P2 = LpVariable("P2", 0, 30)
P3 = LpVariable("P3", 0, None)  # 无上限则保持None
P4 = LpVariable("P4", 0, 30)
P5 = LpVariable("P5", 0, None)

# 二进制变量（互斥控制）
y1 = LpVariable("y1", cat="Binary")
y2 = LpVariable("y2", cat="Binary")
y3 = LpVariable("y3", cat="Binary")
y4 = LpVariable("y4", cat="Binary")
y5 = LpVariable("y5", cat="Binary")

# 目标函数
prob += 1*y1 + 1.5*y2 + 1.7*y3 + 2*y4 + 2.5*y5, "Z"

# 约束条件
# 总和约束：此时仅选中的P变量会贡献值，未选中的为0
prob += P1 + P2 + P3 + P4 + P5 <= 50, "Total-Constraint"

# 大M法约束：关联P变量与y变量
# P1的原下限10，上限20
prob += P1 <= 20 * y1, "P1_Upper"
prob += P1 >= 10 * y1, "P1_Lower"
# P2的原下限20，上限30
prob += P2 <= 30 * y2, "P2_Upper"
prob += P2 >= 20 * y2, "P2_Lower"
# P3的原下限30，无上限
prob += P3 >= 30 * y3, "P3_Lower"
# P4的原下限15，上限30
prob += P4 <= 30 * y4, "P4_Upper"
prob += P4 >= 15 * y4, "P4_Lower"
# P5的原下限30，无上限
prob += P5 >= 30 * y5, "P5_Lower"

# 互斥约束
prob += y1 + y2 + y3 == 1, "Mutual-Exclusivity-1"
prob += y4 + y5 == 1, "Mutual-Exclusivity-2"

# 求解问题
prob.solve(PULP_CBC_CMD(msg=1))

# 输出结果
print(f"Status: {LpStatus[prob.status]}")
for v in prob.variables():
    print(f"{v.name}: {v.varValue}")
print(f"Optimal Value of the Objective Function: {value(prob.objective)}")

# 计算实际投资值（选中的P变量值，未选中的为0）
print(f"P1 Investment: {value(P1)}")
print(f"P2 Investment: {value(P2)}")
print(f"P3 Investment: {value(P3)}")
print(f"P4 Investment: {value(P4)}")
print(f"P5 Investment: {value(P5)}")

运行结果示例 #

Status: Optimal
P1: 0.0
P2: 20.0
P3: 0.0
P4: 0.0
P5: 30.0
y1: 0.0
y2: 1.0
y3: 0.0
y4: 0.0
y5: 1.0
Optimal Value of the Objective Function: 4.0
P1 Investment: 0.0
P2 Investment: 20.0
P3 Investment: 0.0
P4 Investment: 0.0
P5 Investment: 30.0

此结果中，选中y2和y5，对应P2=20、P5=30，总和50刚好满足约束，目标函数值4.0为当前最优解。

内容的提问来源于stack exchange，提问作者wizardjoe