使用OrTools在Python中求解最大集合装填问题

你的问题属于最大集合装填（Maximal Set Packing）的对偶问题——最小化不相交子集族的数量，本质等价于干扰图的最小着色问题：每个集合对应一个顶点，相交集合间连边，我们需要用最少的颜色（组）为顶点着色，保证相邻顶点颜色不同。由于问题规模极大（15万集合），精确求解不现实，以下是结合OrTools CP-SAT求解器的启发式优化方案，能在可控时间内获得比原贪心更优的解。

方案思路 #

1. 先用原贪心算法快速得到一个初始解（组分配），作为CP-SAT求解的起点，减少求解时间。
2. 基于初始解，用CP-SAT求解器尝试调整集合的组分配，逐步减少总组数。
3. 采用增量式约束构建，避免一次性加载所有冲突关系导致内存溢出。

OrTools实现代码 #

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

# 问题实例参数
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 greedy_pack(sets):
    group_assign = []  # 每个集合对应的组号
    groups = []
    for s in tqdm(sets, desc="Greedy initial packing"):
        assigned = False
        for idx, g in enumerate(groups):
            if not g & s:
                g.update(s)
                group_assign.append(idx)
                assigned = True
                break
        if not assigned:
            groups.append(set(s))
            group_assign.append(len(groups)-1)
    return group_assign, len(groups)

# 预处理：建立元素到集合ID的映射，快速查询冲突集合
element_to_sets = {}
for set_id, s in enumerate(sets):
    for elem in s:
        if elem not in element_to_sets:
            element_to_sets[elem] = []
        element_to_sets[elem].append(set_id)

# 获取一个集合的所有冲突集合ID
def get_conflicts(set_id):
    s = sets[set_id]
    conflicts = set()
    for elem in s:
        conflicts.update(element_to_sets[elem])
    conflicts.remove(set_id)
    return conflicts

# 用CP-SAT优化初始解
def optimize_with_ortools(initial_assign, initial_num_groups):
    model = cp_model.CpModel()
    num_sets = len(initial_assign)
    # 变量：每个集合的组号，初始范围是0到initial_num_groups-1，后续逐步缩小
    group_vars = [model.NewIntVar(0, initial_num_groups-1, f"set_{i}") for i in range(num_sets)]
    
    # 设置初始解作为起点
    for i in range(num_sets):
        model.AddHint(group_vars[i], initial_assign[i])
    
    # 添加约束：冲突的集合不能在同一组
    for set_id in tqdm(range(num_sets), desc="Adding conflict constraints"):
        conflicts = get_conflicts(set_id)
        for conflict_id in conflicts:
            if conflict_id > set_id:  # 避免重复添加约束
                model.Add(group_vars[set_id] != group_vars[conflict_id])
    
    # 目标：最小化最大组号（即总组数）
    max_group = model.NewIntVar(0, initial_num_groups-1, "max_group")
    model.AddMaxEquality(max_group, group_vars)
    model.Minimize(max_group)
    
    # 求解器配置：针对大规模问题调整参数
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 300  # 限制求解时间，可根据需求调整
    solver.parameters.num_search_workers = 8  # 启用多线程
    solver.parameters.linearization_level = 0  # 减少线性化开销
    solver.parameters.log_search_progress = True
    
    # 求解
    status = solver.Solve(model)
    
    # 提取结果
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        optimized_assign = [solver.Value(var) for var in group_vars]
        optimized_num_groups = solver.Value(max_group) + 1
        return optimized_assign, optimized_num_groups
    else:
        print("求解失败，返回初始解")
        return initial_assign, initial_num_groups

# 运行流程
shuffle(sets)
initial_assign, initial_num_groups = greedy_pack(sets)
print(f"贪心解组数：{initial_num_groups}")

optimized_assign, optimized_num_groups = optimize_with_ortools(initial_assign, initial_num_groups)
print(f"优化后组数：{optimized_num_groups}")

# 验证解的正确性
# 构建优化后的组集合
optimized_groups = [set() for _ in range(optimized_num_groups)]
for set_id, group_id in enumerate(optimized_assign):
    s = sets[set_id]
    assert not optimized_groups[group_id] & s, "冲突集合被分配到同一组"
    optimized_groups[group_id].update(s)
assert sum(len(g) for g in optimized_groups) == sum(len(s) for s in sets), "元素总数不匹配"

说明 #

• 内存优化：通过元素到集合的反向映射，避免预存储所有冲突对，而是按需查询冲突集合，减少内存占用。
• 求解效率：以贪心解作为初始提示，帮助CP-SAT快速找到更优解；限制求解时间，平衡解质量和运行速度。
• 可调整参数：可以修改solver.parameters.max_time_in_seconds来控制求解时长，时间越长可能得到的解越优。

内容的提问来源于stack exchange，提问作者Changed My Name Again