Skip to content

Set-Cover Analysis

Coverage optimization model — instantiates Target-Complete Mapping Design

Selects the smallest or cheapest set of sources whose combined reach covers every required target — turning 'cover everything' into a solvable optimization and exposing targets no source can reach.

When many sources can each reach many targets, "cover everything" is not a slogan but an optimization problem. Set-Cover Analysis takes each candidate source's coverage set — the targets it can reach — and chooses a minimum-cost subset of sources whose union covers the entire required target space. Its defining move is to treat completeness as a hard constraint and cost as the objective: the cheapest selection that leaves no target uncovered. In doing so it both proves that a complete cover is achievable from the valid source space and, just as usefully, exposes any target that appears in no candidate's coverage set — a genuine gap no selection can close.

Example

A retailer wants every store to receive next-day delivery from at least one warehouse. Each candidate warehouse site has a coverage set: the stores it can reach overnight. Set-Cover Analysis searches for the fewest warehouses whose combined coverage sets include every store. It returns a four-warehouse selection that covers all but three remote stores — and those three appear in no candidate site's coverage set at all. That is not an optimization failure; it is a real coverage gap that the current source space cannot meet at any price. The outcome is clean: build the four warehouses, and escalate the three unreachable stores as targets requiring a new source or an authorized, explicit exclusion — never a silent drop.

How it works

What distinguishes this model is union-to-cover optimization over coverage sets. Each source is represented by its target coverage set; the model minimizes selected-source cost subject to every target belonging to at least one selected set. Because exact set cover is computationally hard, the workhorse is a greedy heuristic — repeatedly select the source that covers the most still-uncovered targets — which carries a known approximation guarantee.[1] Targets in no source's set fall out of the first pass as hard gaps, distinct from targets that are merely not-yet-selected.

Tuning parameters

  • Objective — minimize source count, minimize weighted cost, or maximize covered value. This defines what "minimum" means.
  • Coverage multiplicity — require each target covered ≥1 time (base contract) or ≥k times, the latter feeding a redundancy requirement.
  • Target weighting — prioritize high-value targets when full cover is infeasible, turning the problem into weighted or partial set cover.
  • Exact vs heuristic — greedy speed on large instances vs optimal cost on small ones.
  • Source-cost model — fixed cost per source vs marginal cost, which shifts which selection is "cheapest."

When it helps, and when it misleads

Its strength is making "cover everything" both concrete and economical, and cleanly separating "no source selected" (fixable by choosing more) from "no source can" (a real gap needing a new source). Its failure mode is that it is only as honest as the coverage sets fed in: if a source's claimed reach is nominal — never load-tested or validated — the model happily "covers" targets that are not really served, and minimizing sources can strip out the redundancy that resilience needs. The classic misuse is feeding optimistic coverage sets to drive the warehouse count down. The discipline that guards against it is to validate the coverage sets — witness validity and capacity — before trusting the cover, and to add a multiplicity constraint wherever resilience matters.

How it implements the components

Set-Cover Analysis realizes the source-selection-and-contract slice of the archetype — the components an optimization over reach can fill:

  • valid_source_space — the candidate sources it selects among; the model both draws from this space and reveals when it is insufficient to cover the targets.
  • target_coverage_contract — it enforces the base contract (every target covered by ≥1 selected source) as its optimization constraint, and tests whether that contract is even feasible.

It does not define the individual source→target links it consumes (that's Test-Case-to-Requirement Linker and Capability–Case Crosswalk), verify a selected source can bear its assigned load (Source Capacity Load Test), or guarantee independent redundant witnesses (Redundancy N+1 Check).

  • Instantiates: Target-Complete Mapping Design — it proves a complete cover is achievable (or not) from the available sources, at minimum cost.
  • Consumes: Bipartite Coverage Matrix — supplies each source's coverage set, the input the optimization runs over.
  • Sibling mechanisms: Source Capacity Load Test · Redundancy N+1 Check · Bipartite Coverage Matrix · Service-Area Gap Analysis · Coverage Counterexample Search

References

[1] The set cover problem — choose the fewest sets whose union is the whole universe — is NP-hard; the greedy algorithm that repeatedly picks the set covering the most still-uncovered elements achieves a ln(n) approximation ratio, which is essentially the best any efficient algorithm can guarantee. That is why greedy is the practical workhorse and why the model's numbers are near-optimal, not exact. ↩