Решение упаковки максимального набора с помощью OrTools в Python ⇐ Python

[Anonymous]

У меня есть список наборов, которые мне нужно сгруппировать в попарно непересекающиеся
семейства. Я знаю, что это проблема упаковки множеств, подобная максимально
независимому множеству и, следовательно, NP-трудная. Один из способов решения этой проблемы — преобразовать его
в интерференционный граф, чтобы каждое множество было вершиной и существовало
ребро между вершинами, если множества пересекаются. Тогда задача
сводится к раскраске графа. Однако граф интерференции для моих экземпляров
проблемы слишком велик, что делает этот подход невозможным.
Вот мое жадное решение Python:

Код: Выделить всё

from random import randint, sample, shuffle
from tqdm import tqdm

# Tweak these constants to vary the problem instances
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 pack_sets(sets):
groups = []
for s in tqdm(sets):
for g in groups:
if not g & s:
g.update(s)
break
else:
groups.append(set(s))
return groups

for _ in range(10):
shuffle(sets)
groups = pack_sets(sets)
assert sum(len(g) for g in groups) == sum(len(s) for s in sets)
# We want to minimize this
print(len(groups))

Это достаточно быстро, но качество решений довольно плохое. Может
кто-нибудь помочь мне переписать его с помощью OrTools, который, как я считаю,
должен давать гораздо лучшие решения?