本文详解如何将 pyomo 模型中由两个二元变量乘积（如 x[i] * x[j]）引发的非线性约束，通过引入辅助变量和经典线性化技巧，严格转化为等价的线性约束，确保模型可被标准 mip 求解器（如 cbc、gurobi）高效求解。
本文详解如何将 pyomo 模型中由两个二元变量乘积（如 x[i] * x[j]）引发的非线性约束，通过引入辅助变量和经典线性化技巧，严格转化为等价的线性约束，确保模型可被标准 mip 求解器（如 cbc、gurobi）高效求解。
在调度类优化问题（如护理人员排班）中，常需建模“若两名客户会话被同一护理员承接，则需计入二者间的通勤时间”。这类逻辑天然涉及二元变量的乘积项（例如 SESSION_ASSIGNED[case1, c] * SESSION_ASSIGNED[case2, c]），而 Pyomo 的线性求解器（如 SolverFactory('cbc')）无法处理非线性表达式，直接报错 Cannot transform nonlinear expression。
核心问题在于原约束中的二次项：
model.SESSION_ASSIGNED[case[0], caregiver] * model.SESSION_ASSIGNED[case[1], caregiver]
该乘积仅在 两个会话均被分配给同一护理员时为 1，否则为 0 —— 这正是典型的逻辑与（AND）关系，完全可通过线性约束精确建模。
✅ 标准线性化方法：引入辅助二元变量
对每一对会话组合 (i, j) 和每位护理员 c，定义新变量 y[i,j,c] ∈ {0,1}，使其满足：
y_{i,j,c} = x_{i,c} \cdot x_{j,c}
其中 x_{i,c} = model.SESSION_ASSIGNED[i,c]。
该等式可通过以下三组线性约束实现（Big-M 形式，因变量为二元，M=1 即可）：
# 在模型定义阶段添加辅助变量（注意维度）
model.Y_CASE_PAIR = pe.Var(
model.CASE_COMBINATIONS * model.CAREGIVERS,
domain=pe.Binary # 或 pe.NonNegativeReals（见下文优化说明）
)
# 线性化约束：y[i,j,c] = x[i,c] + x[j,c] - 1
def y_lower_bound(model, i, j, c):
return model.Y_CASE_PAIR[i, j, c] >= (
model.SESSION_ASSIGNED[i, c] + model.SESSION_ASSIGNED[j, c] - 1
)
model.y_lb = pe.Constraint(model.CASE_COMBINATIONS * model.CAREGIVERS, rule=y_lower_bound)
✅ 关键优化：y 可松弛为连续变量
由于目标函数（如最小化总通勤时间）是 y 的线性加权和，且系数 COMMUTE[...] ≥ 0（通勤时间为非负），最优解中 y[i,j,c] 必然取极值 0 或 1。因此可安全地将 domain=pe.Binary 替换为 domain=pe.NonNegativeReals 并添加上下界 bounds=(0,1)，显著减少整数变量数量，提升求解效率：model.Y_CASE_PAIR = pe.Var( model.CASE_COMBINATIONS * model.CAREGIVERS, bounds=(0, 1) # 连续变量，但自然取整 )
? 重写原约束：用 y 替代乘积项
将原始非线性约束 commute_care 改写为纯线性形式：
def commute_care_linear(model, caregiver):
commute_expr = sum(
model.Y_CASE_PAIR[case[0], case[1], caregiver] * (
model.CASE_BIGGER[case[1], case[0]] *
model.COMMUTE[(model.IDX_CLIENTS[case[0]], model.IDX_CLIENTS[case[1]])] +
(1 - model.CASE_BIGGER[case[1], case[0]]) *
model.COMMUTE[(model.IDX_CLIENTS[case[1]], model.IDX_CLIENTS[case[0]])]
)
for case in model.CASE_COMBINATIONS
)
return model.COMMUTE_CARE[caregiver] == commute_expr
model.commute_care_cons = pe.Constraint(model.CAREGIVERS, rule=commute_care_linear)
⚠️ 注意事项与最佳实践
对称性剪枝：CASE_COMBINATIONS 包含所有 (i,j) 对（含 i==j 和 (i,j) 与 (j,i)）。但通勤计算中 (i,j) 与 (j,i) 通常不同（有向图），且 i==j 时通勤为 0。建议预过滤：仅保留 i != j 的组合，并根据业务逻辑决定是否使用上三角（i
参数 CASE_BIGGER 可简化：当前用 int(case1 > case2) 判断顺序，实际可直接在 COMMUTE 查表时按会话时间顺序索引，或改用 model.SESSION_START_TIME[i] 等显式时间参数，增强可读性。
内存与规模权衡：Y_CASE_PAIR 维度为 |CASES|² × |CAREGIVERS|。若会话数达千级，需评估内存开销；此时可考虑仅对地理邻近的客户对生成 CASE_COMBINATIONS（稀疏化）。
验证等价性：添加单元测试，枚举小规模 x[i,c] 组合，断言 y[i,j,c] 值与 x[i,c]*x[j,c] 严格一致。
✅ 总结
将 x[i] * x[j]（x 为二元）线性化是整数规划建模的基石技巧。其本质是用线性不等式“围住”乘积的凸包（即 {(0,0,0), (1,0,0), (0,1,0), (1,1,1)}），三约束共同构成紧致（tight）线性表示。在 Pyomo 中，只需三步：
1️⃣ 引入辅助变量 y；
2️⃣ 添加三条线性约束；
3️⃣ 在目标/约束中用 y 替换原乘积项。
此举不仅解决报错，更保障模型可被工业级 MIP 求解器稳定、高效求解，是构建可扩展调度系统的关键一步。
