Solve the set cover problem in Python

Set cover — pick the fewest sets whose union covers every element — models choosing sensor locations to watch every zone, features to hit every requirement, or servers to reach every region. The default answer online is a greedy pass; it approximates but doesn't optimize. With quicopt you get the provably smallest cover in a few lines of Python.

The naive approach

Greedy repeatedly grabs the set covering the most still-uncovered elements. It is simple and often decent, but it can use more sets than necessary and gives no optimality guarantee. Enumerating subsets is exponential. Model it instead.

Model it as a MILP

A binary x[s] selects set s. For every element, at least one selected set must contain it; minimize the number of sets chosen:

from ortools.math_opt.python import mathopt
from quicopt import Client
sets = [{0,1,2},{2,3,4},{4,5,6},{6,7,0},{1,3,5,7},{0,2,4,6}]
universe = set(range(8))
M = len(sets)
model = mathopt.Model(name="set_cover")
x = [model.add_binary_variable(name=f"s{s}") for s in range(M)]
for e in universe:
    model.add_linear_constraint(sum(x[s] for s in range(M) if e in sets[s]) >= 1)
model.minimize(sum(x))
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  2.0
├── x:          s0=0, s1=0, s2=0, s3=0, s4=1, s5=1  (6 variables)
└── solve_time: 0.0138 s

What you get

status: optimal means 2 sets is proven minimal: s4 = {1,3,5,7} and s5 = {0,2,4,6} cover all eight elements with nothing to spare. A greedy pass might have started with a three-element set and needed a third pick; the MILP finds the exact-cover pair and proves it optimal.

Switch the objective to minimize summed set costs and you have weighted set cover — same model, cheapest cover.

Next

• The problem class behind this: Mixed-integer linear (MILP)
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: R. M. Karp, Reducibility Among Combinatorial Problems, in Complexity of Computer Computations, 1972.