🧩 Constraint Solving POTD:Problem of the Day: The Set Cover Problem

[github-actions[bot]]

Problem Statement

The Set Cover Problem is a classic optimization problem asking: given a universe U of n elements and a collection S of m subsets of U, find the minimum number of subsets whose union equals U.

Concrete Example

Imagine a hospital needs to staff an emergency room with doctors who have different specializations:

• Universe: U = {cardiology, trauma, pediatrics, neurology, oncology} (5 specializations needed)
• Available doctors:
  • Dr. Alice: {cardiology, trauma}
  • Dr. Bob: {trauma, pediatrics}
  • Dr. Carol: {neurology, oncology}
  • Dr. Diana: {cardiology, oncology}
  • Dr. Eve: {pediatrics, neurology}

Question: What is the minimum number of doctors needed to cover all specializations?

Solution: Dr. Alice + Dr. Carol + Dr. Bob = 3 doctors cover all five specializations.

Input/Output Specification

• Input: Universe U = {1, 2, ..., n}, collection S = {S_1, S_2, ..., S_m} where each S_i ⊆ U
• Output: A subset I ⊆ {1, ..., m} such that ⋃_{i∈I} S_i = U and |I| is minimized
• Optimization Goal: Minimize the cardinality of the chosen cover

---

Why It Matters

The Set Cover Problem appears in numerous real-world contexts:

• Network Design: Selecting the minimum number of base stations to provide coverage across a geographic region. Each base station covers a set of locations; we want complete coverage with the fewest stations.
• Crew Scheduling: Airlines and transit operators use set cover models to select the minimum number of crew members whose combined qualifications cover all required skills for all flights.
• Facility Location: Choosing warehouses or distribution centers to serve all customer demand with minimum facility count.
• Software Testing: Identifying the minimum set of test cases that exercise all program paths or requirements (test case selection for code coverage).
• Vaccine Distribution: Selecting the minimum set of vaccination clinics to ensure every neighborhood has access within a reasonable distance.

---

Modeling Approaches

Approach 1: Integer Linear Programming (ILP)

Paradigm: Mixed-Integer Programming

Decision Variables:

• x_i ∈ {0, 1} for i = 1, ..., m (binary variable: 1 if subset S_i is chosen, 0 otherwise)

Objective:

Minimize: Σ_{i=1}^{m} x_i

Constraints:

For each element j ∈ U:
  Σ_{i: j ∈ S_i} x_i ≥ 1

Trade-offs:

• Expressiveness: Exact formulation; ILP solvers (CPLEX, Gurobi) find proven optimal solutions.
• Scalability: NP-hard; standard ILP solvers struggle on large instances (hundreds of elements/subsets), but good branch-and-bound heuristics work well for practical sizes.
• Propagation: Limited automated constraint propagation compared to CP models.

Approach 2: Constraint Programming (CP)

Paradigm: Declarative Constraint Satisfaction with Global Constraints

Decision Variables:

• chosen ⊆ {1, ..., m} (set variable representing which subsets are selected)
• Optional: count = |chosen| (count variable to minimize)

Constraints:

∪_{i ∈ chosen} S_i = U  (set cover global constraint)
Minimize: |chosen|

Or equivalently in array form:

• cover[j] for j ∈ U is a set variable representing which chosen subsets cover element j
• Each cover[j] is non-empty (each element must be covered by at least one subset)

Trade-offs:

• Expressiveness: Elegant declarative model; global constraints like element and set operations are first-class.
• Propagation: Set constraints and cardinality propagation can be very efficient; CP solvers often beat ILP on highly constrained instances.
• Scalability: Good for medium-sized problems; some CP solvers incorporate hybrid techniques (relaxations to ILP).

Example Model (Pseudo-code)

% Pseudo-code (MiniZinc style)
int: n;                    % number of elements
int: m;                    % number of subsets
array[1..m] of set of 1..n: subsets;

var set of 1..m: chosen;   % which subsets to pick
var int: num_chosen = card(chosen);

constraint (union(i in chosen)(subsets[i]) = 1..n);

solve minimize num_chosen;

In Python-inspired pseudocode:

from constraint import Problem

problem = Problem()

# Decision: which subsets to choose (as boolean variables)
for i in range(m):
    problem.addVariable(f"x_{i}", [0, 1])

# Coverage constraint: each element must be covered
for j in range(n):
    covering_subsets = [i for i in range(m) if j in subsets[i]]
    problem.addConstraint(
        lambda *args: sum(args) >= 1,
        tuple(f"x_{i}" for i in covering_subsets)
    )

# Objective: minimize sum of chosen subsets
solutions = problem.getSolutions()
best = min(solutions, key=lambda sol: sum(sol.values()))

---

Key Techniques

1. Greedy Approximation & Relaxation Bounds

The greedy algorithm—repeatedly select the subset covering the most uncovered elements—achieves a ln(n) approximation ratio (where n = |U|). This bound is nearly tight (hardness of approximation); no polynomial-time algorithm achieves better approximation unless P=NP.

For lower bounds, LP relaxation (relax binary x_i to x_i ∈ [0, 1]) gives a fractional cover, which is always a lower bound on the integer optimum.

2. Column Generation for Large-Scale Instances

For problems with many subsets (thousands or millions), column generation decomposes the model:

• Restrict to a subset of columns (subsets) in the master ILP.
• Solve the pricing subproblem to identify high-value subsets (dual variables).
• Iteratively add promising columns until no improvement is found.

This is especially powerful for set cover arising from combinatorial problems (e.g., interval scheduling, transportation).

3. Symmetry Breaking & Dominance Pruning

• Dominated subsets: If subset S_i ⊆ S_j, then S_i is dominated; never include S_i alone when S_j is available.
• Symmetry breaking: If two subsets are identical, treat them as a single choice.
• These reductions shrink the problem size before search, improving solver efficiency dramatically.

---

Challenge Corner

Question 1: Can you formulate Set Cover as a hitting set problem (its dual)? How would the constraint structure change? Would one formulation solve faster than the other on your test instances?

Question 2: Weighted Set Cover generalizes the problem: each subset S_i has a weight w_i, and we minimize total weight instead of count. How would you modify the ILP and CP models? What new algorithms become relevant?

Question 3: Partial Set Cover: Suppose you only need to cover 80% of the elements. How would you adjust your model? What heuristics could guide the search to solutions quickly?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Elsevier. Chapters on set constraints and optimization.

2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 35 covers approximation algorithms, including greedy set cover.

3. Wolsey, L. A. (1998). Integer Programming. Wiley. Covers LP relaxations and cutting-plane methods for combinatorial optimization.

4. Chvátal, V. (1979). "A greedy heuristic for the set-covering problem." Mathematics of Operations Research, 4(3), 233–235. Seminal paper on approximation bounds.

---

Enjoyed this problem? Next week we'll explore a fascinating hybrid approach combining these techniques!

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 8.85 AIC · ⌖ 18.9 AIC · ⊞ 5.5K · ◷

• expires on Aug 5, 2026, 4:10 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #49125.