如何在Pyomo优化模型中添加区域分配的连续性约束？

问题背景 #

需将20个区域分配给4个机构，已知区域-机构出行距离矩阵、区域间邻接关系，通过Pyomo构建优化模型实现分配，目标是最小化服务成本与分配变动成本的加权和，同时要求每个机构分配的区域形成预定义数量的连续集群，需补充实现该集群数量约束。

核心难点 #

邻接关系仅反映区域间直接相邻，而连续集群要求分配给同一机构的区域构成连通集合（任意两个区域可通过同机构的相邻区域路径连接），需将连通性逻辑转化为整数规划可识别的约束。

解决方案：引入辅助变量与连通性约束 #

1. 新增辅助变量 #

在模型中添加两类二进制辅助变量，用于刻画集群的连通性与根节点：

# 辅助变量1：标记区域d是否为机构h的集群根节点
model.IsRoot = Var(model.Institutions, model.Districts, within=Binary)

# 构建相邻区域对集合（过滤自环，避免重复约束）
adjacent_pairs = []
for d1 in model.Districts:
    for d2 in adjacency[d1]:
        if d1 < d2 and d2 in model.Districts:
            adjacent_pairs.append((d1, d2))
model.AdjacentPairs = Set(initialize=adjacent_pairs)

# 辅助变量2：标记相邻区域d1、d2是否同属机构h的同一集群
model.Connect = Var(model.Institutions, model.AdjacentPairs, within=Binary)

2. 定义集群数量参数 #

假设通过cluster_count_df提供每个机构的目标集群数量，添加参数：

# 每个机构的目标集群数量参数
model.TargetClusters = Param(model.Institutions, initialize=cluster_count_df.set_index('institution')['target_clusters'].to_dict())

3. 实现集群约束（替换原代码中Constraint 6的???） #

添加以下约束组：

# 约束6-1：每个机构的集群数量等于目标值
model.ClusterNumber = ConstraintList()
for h in model.Institutions:
    model.ClusterNumber.add(
        sum(model.IsRoot[h, d] for d in model.Districts) == model.TargetClusters[h]
    )

# 约束6-2：根节点必须是分配给该机构的区域
model.RootAssignment = ConstraintList()
for h in model.Institutions:
    for d in model.Districts:
        model.RootAssignment.add(
            model.IsRoot[h, d] <= model.Assign[d, h]
        )

# 约束6-3：相邻区域同属机构h时，要么连通要么分属不同集群
model.ConnectLink = ConstraintList()
for h in model.Institutions:
    for (d1, d2) in model.AdjacentPairs:
        # 仅当d1、d2都分配给h时，连通标记才可生效
        model.ConnectLink.add(model.Connect[h, (d1, d2)] <= model.Assign[d1, h])
        model.ConnectLink.add(model.Connect[h, (d1, d2)] <= model.Assign[d2, h])
        # 若同属h，要么连通，要么其中一个是根节点（分属不同集群）
        model.ConnectLink.add(
            model.Assign[d1, h] + model.Assign[d2, h] - model.Connect[h, (d1, d2)] <= 1 + model.IsRoot[h, d1] + model.IsRoot[h, d2]
        )

# 约束6-4：流量守恒保证集群连通性
model.ConnectFlow = ConstraintList()
for h in model.Institutions:
    for d in model.Districts:
        # 获取d的有效相邻区域
        neighbors = [d_nei for d_nei in adjacency[d] if d_nei != d and (min(d, d_nei), max(d, d_nei)) in model.AdjacentPairs]
        # 非根节点的区域必须至少有一个同机构的连通邻居
        model.ConnectFlow.add(
            sum(model.Connect[h, (min(d, d_nei), max(d, d_nei))] for d_nei in neighbors) >= model.Assign[d, h] - model.IsRoot[h, d]
        )

约束逻辑说明 #

• 根节点数量约束：直接控制每个机构的集群总数，根节点数等于目标集群数。
• 根节点与分配关联：确保根节点必须是该机构负责的区域，避免无效根节点。
• 相邻区域连通约束：保证同机构的相邻区域要么属于同一集群，要么分属不同集群。
• 流量守恒约束：确保每个非根节点的区域至少有一个同机构的连通邻居，从而保证整个集群的连通性。

代码补充说明 #

将上述变量、参数、约束代码插入原Pyomo模型中Constraints 6 - Tolerance on Clusters of Districts的位置即可。需提前准备cluster_count_df，包含institution和target_clusters两列，定义每个机构的目标集群数量。

求解注意事项 #

• 该模型为混合整数规划（MIP），求解时间随规模增大而增加，可通过调整CBC求解器参数（如设置时间限制、启用启发式算法）优化效率。
• 若允许集群数量在范围内波动，可将ClusterNumber约束改为不等式（如<= model.MaxClusters[h]），对应调整参数定义。

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