import itertools
from typing import List

import pyomo.core as pyo

def set_cover(sub_sets: List[List[int]]) -> pyo.ConcreteModel:
entire_set = set(itertools.chain(*sub_sets))
n = max(entire_set)
num_sets = len(sub_sets)
assert entire_set == set(
range(1, n + 1)
), f"the union of the subsets is {entire_set} not equal to range(1, {n + 1})"

model = pyo.ConcreteModel()
model.x = pyo.Var(range(num_sets), domain=pyo.Binary)

@model.Constraint(entire_set)
def independent_rule(model, num):
return sum(model.x[idx] for idx in range(num_sets) if num in sub_sets[idx]) >= 1

model.cost = pyo.Objective(expr=sum(model.x.values()), sense=pyo.minimize)

return model


This function generates a PYOMO model which formulates the Set Cover problem. Given a set of numbers {1, 2, ..., n}, and a collection of subsets whose union equals the set, determine the smallest sub-collection whose union equals the set. The model consists of:

• Binary variable for each subset (model.x) indicating how if it is included in the sub-collection.
• Objective rule – size of the sub-collection.
• Constraint - the sub-collection should cover the original set.