问题背景梳理 #

你现在碰到的是一个带强约束的群组优化难题：要把93人拆分成5-10人的小组，核心规则是：

• 亲和度为5的两人必须同组
• 亲和度为0的两人绝对不能同组
• 最终要最大化组内的总亲和度

当前用OR-Tools CP-SAT的代码要么跑不出结果，要么强制生成等大小组，进度更新也失效，你还在纠结要不要换成PuLP。下面我帮你拆解问题、优化代码，再对比两个工具的适配性。

先揪出当前代码的核心问题 #

1. 进度回调完全失效的原因

你的ProgressCallback只在找到可行解时才会触发，但如果模型一开始就找不到可行解，或者长时间搜不到第一个可行解，这个回调就会一直沉默。你自然看不到任何进度提示。

2. 无解/强制等分组的可能诱因

• 约束冲突：先检查你的亲和度矩阵！比如有没有出现「A必须和B同组，B必须和C同组，但A和C不能同组」的矛盾情况？这种逻辑冲突会直接导致无解。
• 最大组数计算不合理：93人用num_people // min_size得到18组，但18组的最小总人数是90，剩下3人没地方放？不对，你的组大小约束是允许5-10人的，但求解器可能在搜索时优先尝试等大小组，导致陷入局部最优。
• 目标函数效率极低：你用AddMultiplicationEquality计算每对同组的亲和度，93人会生成4000+个乘法约束，这会让求解器的搜索速度暴跌。

针对OR-Tools代码的优化方案 #

我重写了核心部分，解决了上述问题，还加了更实用的进度反馈：

from ortools.sat.python import cp_model
import numpy as np
import pandas as pd
import time

def load_affinity_matrix(file_path):
    df = pd.read_excel(file_path, index_col=0)
    return df.to_numpy(), df.index.tolist()

def optimize_groups(affinity_matrix, people_names, min_size=5, max_size=10):
    num_people = len(affinity_matrix)
    model = cp_model.CpModel()
    
    # 调整最大组数：留出足够灵活度，允许组大小变化
    max_groups = num_people // min_size  # 93人对应18组（最多18个5人组）
    min_groups = (num_people + max_size - 1) // max_size  # 93人对应10组（最少10个9/10人组）
    print(f"允许组数范围：{min_groups}~{max_groups}组")

    # 决策变量：x[i][g] = 1表示第i个人在第g组
    x = {}
    for i in range(num_people):
        for g in range(max_groups):
            x[i, g] = model.NewBoolVar(f'x_{i}_{g}')
    
    # 约束1：每个人必须且只能在一个组
    for i in range(num_people):
        model.AddExactlyOne(x[i, g] for g in range(max_groups))
    
    # 约束2：组大小控制（允许空组，但非空组必须在5-10人之间）
    for g in range(max_groups):
        group_has_people = model.NewBoolVar(f'group_{g}_has_people')
        # 组有人 → 大小在5-10之间
        model.Add(sum(x[i, g] for i in range(num_people)) >= min_size).OnlyEnforceIf(group_has_people)
        model.Add(sum(x[i, g] for i in range(num_people)) <= max_size).OnlyEnforceIf(group_has_people)
        # 组没人 → 大小为0
        model.Add(sum(x[i, g] for i in range(num_people)) == 0).OnlyEnforceIf(group_has_people.Not())
    
    # 约束3：亲和度规则
    for i in range(num_people):
        for j in range(i + 1, num_people):
            score = affinity_matrix[i][j]
            if score == 5:
                # 必须同组：i和j在所有组的归属完全一致
                for g in range(max_groups):
                    model.Add(x[i, g] == x[j, g])
            elif score == 0:
                # 不能同组：i和j不能同时在同一个组
                for g in range(max_groups):
                    model.Add(x[i, g] + x[j, g] <= 1)
    
    # 优化目标：最大化组内总亲和度（简化实现，减少约束数量）
    total_affinity = 0
    for i in range(num_people):
        for j in range(i + 1, num_people):
            if affinity_matrix[i][j] > 0:
                # 用sum(x[i][g] * x[j][g])表示i和j是否同组（0或1）
                same_group = sum(x[i, g] * x[j][g] for g in range(max_groups))
                total_affinity += affinity_matrix[i][j] * same_group
    model.Maximize(total_affinity)
    
    # 求解器配置：开启进度日志，设置超时
    solver = cp_model.CpSolver()
    solver.parameters.num_search_workers = 8
    solver.parameters.max_time_in_seconds = 3600  # 1小时超时
    solver.parameters.log_search_progress = True  # 内置进度日志，即使没找到解也能看到搜索状态

    # 自定义回调：找到可行解就打印进度
    class SolutionCallback(cp_model.CpSolverSolutionCallback):
        def __init__(self, people_names, max_groups):
            super().__init__()
            self.people_names = people_names
            self.max_groups = max_groups
            self.solution_count = 0
            self.start_time = time.time()

        def on_solution_callback(self):
            self.solution_count += 1
            elapsed = round(time.time() - self.start_time, 2)
            print(f"\n找到第{self.solution_count}个可行解，耗时{elapsed}秒")
            # 打印当前组大小分布
            groups = [[] for _ in range(self.max_groups)]
            for idx, name in enumerate(self.people_names):
                for g in range(self.max_groups):
                    if self.Value(x[idx, g]) == 1:
                        groups[g].append(name)
            non_empty = [g for g in groups if g]
            print(f"当前非空组：{len(non_empty)}个，组大小：{[len(g) for g in non_empty]}")

    callback = SolutionCallback(people_names, max_groups)
    print("开始优化...")
    status = solver.Solve(model, callback)
    print(f"\n求解完成！状态：{solver.StatusName(status)}，总耗时{round(time.time() - callback.start_time, 2)}秒")

    # 提取结果
    if status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
        groups = [[] for _ in range(max_groups)]
        for idx, name in enumerate(people_names):
            for g in range(max_groups):
                if solver.Value(x[idx, g]) == 1:
                    groups[g].append(name)
        return [g for g in groups if g]  # 过滤空组
    else:
        print("未找到任何可行解，请检查约束是否冲突！")
        return None

# 示例调用
if __name__ == "__main__":
    affinity_matrix, people_names = load_affinity_matrix('/Users/myname/Documents/affinity_matrix.xlsx')
    result_groups = optimize_groups(affinity_matrix, people_names)
    if result_groups:
        print("\n最终分组结果：")
        for idx, group in enumerate(result_groups, 1):
            print(f"组{idx}（{len(group)}人）：{', '.join(group)}")

优化点说明

1. 进度反馈修复：开启内置的log_search_progress，即使没找到解也能看到求解器的搜索进度（分支数、冲突数）；自定义回调会在找到可行解时立即打印组分布。
2. 组大小约束更灵活：允许空组，非空组严格遵守5-10人限制，避免求解器强制等大小组。
3. 目标函数简化：直接用sum(x[i][g] * x[j][g])表示两人是否同组，减少不必要的中间变量。
4. 参数调整：设置超时时间，避免无限等待。

PuLP vs OR-Tools：哪个更适合你？ #

1. PuLP的优势

• 建模更贴近线性规划思维，适合有线性约束的问题，代码可读性高。
• 支持多种求解器：免费的CBC，商业的Gurobi/CPLEX（后者性能极强，但需要授权）。
• 对于你的问题，完全可以用PuLP建模：组归属变量是0-1变量，约束都是线性的，目标函数也是线性的。

2. OR-Tools CP-SAT的优势

• 免费且开源，不需要额外授权。
• 更擅长处理布尔逻辑约束（比如必须同组/不能同组的规则），搜索效率在纯免费工具里属于第一梯队。
• 对于大规模布尔变量问题，CP-SAT的分支定界算法可能比CBC更快。

3. 推荐选择

先尝试修改后的OR-Tools代码，重点检查亲和度矩阵有没有约束冲突（比如用10人小数据集测试）。如果还是无法生成可行解，再尝试用PuLP建模，若能用到商业求解器（比如Gurobi），性能会有质的提升。

备注：内容来源于stack exchange，提问作者anon_group_optimizer