如何使用OrTools在Python中改进最大集合装箱（set packing）问题的求解效果

阿华AIGC实验室

2026-4-27

使用OrTools优化集合装箱问题的解决方案

你提到的集合装箱问题确实是NP-hard的，你的贪心算法虽然运行速度快，但解质量容易陷入局部最优。OrTools的CP-SAT求解器非常适合这类组合优化问题，能在合理时间内找到远优于贪心算法的解。下面是基于OrTools的实现，我会详细拆解每一步的思路：

核心思路

集合装箱的目标是用最少的两两不相交集合族覆盖所有输入集合，等价于在干扰图中寻找最小着色数（干扰图中相邻节点不能同色，每个颜色对应一个集合族）。OrTools的CP-SAT求解器通过建模约束和目标函数，能高效搜索最优或近似最优解。

实现步骤与代码

from ortools.sat.python import cp_model
from random import randint, sample, shuffle
import itertools

# 生成问题实例（和你的原代码逻辑一致）
N_SETS = 150_000
LO, HI = 100, 300
DOMAIN = list(range(150_000))
sets = [set(sample(DOMAIN, k=randint(LO, HI))) for _ in range(N_SETS)]

def optimize_set_packing(sets, time_limit_seconds=600):
    # 预处理：快速找出所有有交集的集合对（优化大规模数据的计算效率）
    print("预处理冲突集合对...")
    element_to_sets = {}
    for idx, s in enumerate(sets):
        for elem in s:
            if elem not in element_to_sets:
                element_to_sets[elem] = []
            element_to_sets[elem].append(idx)
    
    # 收集去重后的冲突对
    conflicting_pairs = set()
    for elem in element_to_sets:
        # 共享同一元素的集合两两冲突
        for pair in itertools.combinations(element_to_sets[elem], 2):
            conflicting_pairs.add(tuple(sorted(pair)))
    conflicting_pairs = list(conflicting_pairs)
    print(f"共识别到 {len(conflicting_pairs)} 对冲突集合")

    # 初始化CP-SAT模型
    model = cp_model.CpModel()
    num_sets = len(sets)

    # 定义变量：每个集合对应的组号，初始范围设为0到集合总数（求解器会自动缩小范围）
    group_vars = [model.NewIntVar(0, num_sets - 1, f"set_{i}_group") for i in range(num_sets)]

    # 添加约束：有交集的集合不能分配到同一组
    print("添加约束条件...")
    for (i, j) in conflicting_pairs:
        model.Add(group_vars[i] != group_vars[j])

    # 定义目标函数：最小化使用的组数量（组号从0开始，所以最大组号+1就是总组数）
    max_group = model.NewIntVar(0, num_sets - 1, "max_group")
    model.AddMaxEquality(max_group, group_vars)
    model.Minimize(max_group + 1)

    # 配置求解器参数
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = time_limit_seconds  # 设置时间限制，平衡解质量和速度
    solver.parameters.num_search_workers = 8  # 启用并行求解，根据CPU核心数调整
    solver.parameters.log_search_progress = True  # 可选：打印搜索进度

    # 启动求解
    print("开始求解...")
    status = solver.Solve(model)

    # 处理求解结果
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        result_type = "最优解" if status == cp_model.OPTIMAL else "高质量可行解"
        print(f"求解状态: {result_type}")
        print(f"使用的组数量: {solver.Value(max_group) + 1}")
        
        # 整理分组结果
        groups = {}
        for i in range(num_sets):
            group_id = solver.Value(group_vars[i])
            if group_id not in groups:
                groups[group_id] = set()
            groups[group_id].update(sets[i])
        
        # 验证结果正确性
        total_elements = sum(len(s) for s in sets)
        assert sum(len(g) for g in groups.values()) == total_elements
        
        return groups.values()
    else:
        print("未找到可行解")
        return None

# 运行优化（可多次运行，利用求解器的随机性探索更优解）
for _ in range(2):
    shuffle(sets)
    groups = optimize_set_packing(sets, time_limit_seconds=300)
    if groups:
        print(f"最终组数量: {len(groups)}")