Pyomo非线性约束线性化求助：护理人员排班通勤约束改造

现有模型组件 #

以下是约束涉及的核心模型组件（基于Pyomo实现）：

1. 班次组合集合 CASE_COMBINATIONS #

由所有班次ID的笛卡尔积构成，用于枚举所有可能的班次配对：

model.CASE_COMBINATIONS = pe.Set(
    initialize=product(
        self.df_sessions["idx"].unique(),
        self.df_sessions["idx"].unique(),
    ),
    dimen=2,
)

2. 班次分配二元变量 SESSION_ASSIGNED #

表示护理人员是否被分配至某班次，(session, caregiver) 元组取值为1（分配）或0（未分配）：

model.TASKS = pe.Set(
    initialize=model.CASES * model.CAREGIVERS, dimen=2
)

model.SESSION_ASSIGNED = pe.Var(model.TASKS, domain=pe.Binary)

3. 班次顺序参数 CASE_BIGGER #

判断班次配对中两个班次的先后顺序，(case1, case2) 取值为1表示case1的ID大于case2，否则为0：

model.CASE_BIGGER = pe.Param(
    model.CASE_COMBINATIONS, initialize=self._generate_case_bigger()
)

def _generate_case_bigger(self):
    case_bigger = {}
    for case1, case2 in product(
        self.df_sessions["idx"].unique(), self.df_sessions["idx"].unique()
    ):
        case_bigger[(case1, case2)] = int(case1 > case2)
    return case_bigger

4. 通勤时间参数 COMMUTE #

存储不同客户地点间的通勤时长，对应(client1, client2)的通勤时间：

model.COMMUTE = pe.Param(
    model.CLIENT_CONNECTIONS,
    initialize=self._generate_clients_commute(),
)

非线性约束问题 #

当前用于计算护理人员总通勤时间的约束存在非线性问题，报错原因是表达式中包含两个二元变量的乘积：

def commute_care(model, caregiver):
    commute_expr = sum(
        [
            model.SESSION_ASSIGNED[case[0], caregiver] *
            model.SESSION_ASSIGNED[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

该约束的逻辑是：遍历所有班次组合，若同一护理人员被分配了某对班次，则计算两者间的通勤时间并求和，最终得到总通勤时间。但SESSION_ASSIGNED的乘积项导致表达式非线性，无法用于线性规划求解。

线性化解决方案 #

通过引入辅助二元变量将非线性乘积转化为线性约束，具体步骤如下：

步骤1：定义辅助变量 #

新增二元变量 X[case1, case2, caregiver]，表示护理人员同时被分配了case1和case2两个班次：

# 定义辅助变量的集合：班次组合 × 护理人员
model.COMMUTE_PAIRS = pe.Set(
    initialize=model.CASE_COMBINATIONS * model.CAREGIVERS,
    dimen=3
)

# 辅助二元变量：X[case1, case2, c] = 1 当且仅当护理人员c同时被分配case1和case2
model.X = pe.Var(model.COMMUTE_PAIRS, domain=pe.Binary)

步骤2：添加线性化约束 #

为辅助变量添加约束，确保其与SESSION_ASSIGNED的逻辑一致性：

def linearize_product(model, case1, case2, caregiver):
    # 约束1：X ≤ SESSION_ASSIGNED[case1, c]
    yield model.X[case1, case2, caregiver] <= model.SESSION_ASSIGNED[case1, caregiver]
    # 约束2：X ≤ SESSION_ASSIGNED[case2, c]
    yield model.X[case1, case2, caregiver] <= model.SESSION_ASSIGNED[case2, caregiver]
    # 约束3：X ≥ SESSION_ASSIGNED[case1, c] + SESSION_ASSIGNED[case2, c] - 1
    yield model.X[case1, case2, caregiver] >= model.SESSION_ASSIGNED[case1, caregiver] + model.SESSION_ASSIGNED[case2, caregiver] - 1

model.LinearizeProduct = pe.Constraint(model.COMMUTE_PAIRS, rule=linearize_product)

步骤3：重构通勤时间约束 #

用辅助变量X替换原来的乘积项，得到线性的总通勤时间表达式：

def commute_care_linear(model, caregiver):
    commute_expr = sum(
        model.X[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
        # 可选：过滤掉同一班次的配对（通勤时间为0，不影响结果）
        if case[0] != case[1]
    )
    return model.COMMUTE_CARE[caregiver] == commute_expr

model.CommuteCareLinear = pe.Constraint(model.CAREGIVERS, rule=commute_care_linear)

优化说明 #

• 可以过滤掉case[0] == case[1]的配对，因为同一班次的通勤时间为0，无需计算，减少约束和变量数量。
• 若班次组合存在对称性（如(case1, case2)和(case2, case1)），还可进一步优化，只保留其中一组，避免重复计算。

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