如何使用 Python OR-Tools 优化两两不相交的集合分组？
可以使用 OR-Tools 的 CP-SAT：为每个集合建立一个表示组号的整数变量，再对包含同一元素的所有集合施加 AllDifferent 约束，就能表达完整的分组条件，无须先生成冲突图的所有边。
不过，150,000 个集合构成的完整模型仍可能非常大，换成 OR-Tools 也不能保证在可接受的时间内得到更好的解。可以保留贪心结果作为可行解，先在小规模数据上验证模型，再用 CP-SAT 优化其中若干组。
先明确：目标是最少分组
需要把所有输入集合分配到组中，并尽量减少组数。这对应冲突图的最小图着色问题。
Maximum set packing 的目标是选出尽可能多的两两不相交集合，得到的是一个子族。它与当前问题有关，但目标不同。Maximal 只表示无法再加入集合，不意味着集合数量最大，更不意味着最终分组数量最少。
原来的贪心算法相当于 first-fit coloring：按给定顺序，把每个集合放入第一个可用组。随机打乱顺序可能改变结果，但算法不会主动调整之前的分配。
用元素倒排索引表达冲突
设输入集合为 (S_0,\ldots,S_{n-1})，集合 (S_i) 的组号为 (c_i)。对每个元素 (e)，建立倒排列表：
[ I_e={i\mid e\in S_i}. ]
包含同一个元素的集合必须分到不同组，因此添加：
[ \operatorname{AllDifferent}(c_i
\in I_e). ]这等价于要求组内集合两两不相交：两个集合只要相交，就至少有一个公共元素，对应的约束会要求它们的组号不同。
设贪心方案使用了 (U) 个组，可以限制：
[ 0\le c_i<U, \qquad \min\left(1+\max_i c_i\right). ]
组号允许重新编号，因此这个目标与最小化组数具有相同的最优值。OR-Tools 的 add_all_different 和 add_max_equality 可以直接表达上述约束。接口文档
Python 建模示例
下面的实现先生成贪心方案，再将其组数作为上界、组号作为求解提示。返回的每个组保存原始集合的索引，方便后续移动集合和检查分配。
建议先将示例用于较小实例或局部子问题，不建议直接将完整的 150,000 个集合投入求解。
from collections import defaultdict
from ortools.sat.python import cp_model
def pack_sets_cp(sets, time_limit=30.0):
n = len(sets)
if n == 0:
return [], "EMPTY"
# Build a feasible first-fit assignment.
unions = []
initial_groups = []
initial_colors = []
for i, s in enumerate(sets):
for color, union in enumerate(unions):
if union.isdisjoint(s):
union.update(s)
initial_groups[color].append(i)
initial_colors.append(color)
break
else:
initial_colors.append(len(unions))
unions.append(set(s))
initial_groups.append([i])
upper_bound = len(initial_groups)
del unions
by_element = defaultdict(list)
for i, s in enumerate(sets):
for element in s:
by_element[element].append(i)
lower_bound = max(
(len(indices) for indices in by_element.values()),
default=1,
)
model = cp_model.CpModel()
colors = [
model.new_int_var(0, upper_bound - 1, f"color_{i}")
for i in range(n)
]
for indices in by_element.values():
if len(indices) > 1:
model.add_all_different([colors[i] for i in indices])
max_color = model.new_int_var(
lower_bound - 1, upper_bound - 1, "max_color"
)
model.add_max_equality(max_color, colors)
model.minimize(max_color)
# Group labels are interchangeable.
model.add(colors[0] == 0)
for variable, value in zip(colors, initial_colors):
model.add_hint(variable, value)
model.add_hint(max_color, upper_bound - 1)
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = time_limit
status = solver.solve(model)
status_name = solver.status_name(status)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
groups = defaultdict(list)
for i, variable in enumerate(colors):
groups[solver.value(variable)].append(i)
return list(groups.values()), status_name
if status == cp_model.UNKNOWN:
return initial_groups, "UNKNOWN; returned greedy solution"
raise RuntimeError(f"Unexpected solver status: {status_name}")add_hint 提供搜索线索，但不保证求解器及时接收或返回该解。因此，代码单独保留了贪心方案，在 UNKNOWN 时回退到该方案。
FEASIBLE 表示已经找到可行解，但没有证明最优；OPTIMAL 表示求解器报告已达到最优。不能把超时后的 UNKNOWN 当作无解，也不能在该状态下直接读取变量值。求解状态说明
为什么完整模型仍可能很难求解？
按照题目中的随机生成方式，每个集合的期望大小是 200，总元素出现次数的期望值为：
[ 150{,}000\times200=30{,}000{,}000. ]
这是根据生成参数推导出的期望值，不是实测结果。倒排索引虽然避免了显式生成所有冲突边，但仍要处理大量元素与集合之间的关联；求解器内部还可能产生额外变量和约束。
模型表达更紧凑，内存或搜索成本也不一定足够低。另外，max_time_in_seconds 限制的是求解阶段，前面的 Python 贪心处理、倒排索引构建和模型构建也需要时间与内存。
可以先计算一个成本较低的下界：
[ L=\max_e|I_e|. ]
某个元素出现于多少个集合，这些集合就至少需要多少个不同的组。如果贪心结果的组数等于该下界，就可以证明最优；如果差距较大，则无法用这个下界证明当前方案的质量。
大规模数据如何使用这个模型？
建议把 CP-SAT 用于局部重分组：
- 保存当前方案中每个组包含的原始集合索引。
- 选出若干完整的组，将这些组中的集合交给
pack_sets_cp。 - 如果返回方案使用的组数更少，就替换这些组；否则保留原方案。
- 更换组的组合继续尝试，并记录当前最好的全局方案。
选出的完整组可以独立重新分组，因为不同组之间允许存在交集。只要新的局部方案合法，替换后其他组就不需要改变。
如果选中的集合仍然太多，可以减少每次参与的组数。一次局部求解达到 OPTIMAL，也只证明该子问题的最优性，不能据此声称整个实例已经最优。
保留集合归属信息并检查结果
原函数返回的是每个组的并集，会丢失集合原来的归属关系。保留索引后，可以直接检查每个集合是否恰好分配一次，以及组内是否存在交集：
def validate_groups(sets, groups):
assigned = [False] * len(sets)
for group in groups:
union = set()
for i in group:
assert 0 <= i < len(sets)
assert not assigned[i]
assert union.isdisjoint(sets[i])
assigned[i] = True
union.update(sets[i])
assert all(assigned)这项检查只能确认分组是否合法。要判断是否优于原来的贪心方案，需要在同一批输入上比较组数和总耗时；要判断是否达到最优，则需要有效下界或求解器的最优性证明。
备注：内容仅供参考。