如何用PuLP实现LP问题互斥约束？为何我的实现出现不可行状态？

问题根源 #

你的模型返回**Infeasible（不可行）**的核心原因是：决策变量的固定下界与二进制约束逻辑完全冲突。

• 例如P2被定义为LpVariable("P2", 10, 20)，强制要求10 ≤ P2 ≤20
• 但当二进制变量y2=0时，约束P2 <= y2*10000000000等价于P2 ≤0，这和P2≥10的下界要求直接矛盾
• 其他带下界的变量（P3、P4、P6、P7）都存在同样的冲突，导致模型没有任何可行解

互斥约束的正确实现逻辑 #

要实现前3个变量互斥、后2个变量互斥的需求，需明确规则：

• 当二进制变量y=1时，对应决策变量可以取设定的有效上下界范围
• 当y=0时，对应决策变量必须被强制为0（或符合互斥规则的无效值）

修正后的代码 #

from pulp import *

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

# 决策变量：先将下界设为0，后续通过约束绑定有效范围
P2 = LpVariable("P2", 0, 20)
P3 = LpVariable("P3", 0, 30)
P4 = LpVariable("P4", 0, None)
P6 = LpVariable("P6", 0, 30)
P7 = LpVariable("P7", 0, None)

# 二进制变量
y2 = LpVariable("y2", cat="Binary")
y3 = LpVariable("y3", cat="Binary")
y4 = LpVariable("y4", cat="Binary")
y6 = LpVariable("y6", cat="Binary")
y7 = LpVariable("y7", cat="Binary")

# 目标函数
prob += 1*P2 + 1.5*P3 + 1.7*P4 + 2*P6 + 2.5*P7, "Z"

# 总约束
prob += P2 + P3 + P4 + P6 + P7 <= 500000, "Total-Constraint"

# 绑定二进制变量与决策变量的有效范围：选中则变量在原范围内，未选中则为0
# 前3个变量的约束
prob += P2 >= y2 * 10, "P2-Lower-Bound"
prob += P2 <= y2 * 20, "P2-Upper-Bound"

prob += P3 >= y3 * 20, "P3-Lower-Bound"
prob += P3 <= y3 * 30, "P3-Upper-Bound"

prob += P4 >= y4 * 30, "P4-Lower-Bound"

# 后2个变量的约束
prob += P6 >= y6 * 15, "P6-Lower-Bound"
prob += P6 <= y6 * 30, "P6-Upper-Bound"

prob += P7 >= y7 * 30, "P7-Lower-Bound"

# 互斥约束：前3选1，后2选1
prob += y2 + y3 + y4 == 1, "Mutual Exclusivity 1"
prob += y6 + y7 == 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)}")

代码说明 #

• 将所有决策变量的初始下界设为0，避免未选中时的约束冲突
• 为每个决策变量添加与二进制变量绑定的上下界约束：当y=1时，变量满足原有的上下界要求；当y=0时，变量被强制为0
• 保留原互斥约束逻辑，确保同一组内仅一个变量被选中

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