A team must select service locations so that every neighborhood has access to at least one selected location. A cheap location can serve several neighborhoods, so choosing the cheapest location separately for each neighborhood may count the same decision more than once. The useful modeling step is to make one variable per available location, and then write one requirement for each neighborhood. The same structure appears in test selection, facility coverage and choosing sets of tasks.
From coverage to an integer model
Definition 27.1.1
(Weighted set covering)
Let be a finite set of requirements, and let be the requirements covered by choice , for . Let be its cost and put when , and otherwise. The binary variable means that choice is selected. The weighted set-covering problem is
A cover is a feasible , equivalently a collection of sets whose union is .
The inequality says at least one, so overlap is allowed. If a requirement occurs in no set, its row is and the problem is infeasible. Otherwise selecting every set is feasible. A set with no requirements may be discarded when its cost is nonnegative. Demanding equality in every row would instead prohibit overlap: that is a different problem, set partitioning. Replacing the inequalities by gives packing constraints, whose meaning also differs.
Common mistake
(Paying once per requirement instead of once per set)
Choosing the cheapest set for each requirement and adding those costs counts a set once for every requirement it serves. In the first worked example below, the cheapest sets for requirements cost each, giving , while the cover serving the same choices costs . The model pays once through the single variable , however many rows it appears in.
Relaxing integrality gives the linear program , .
Proposition 27.1.2
(Upper bounds are redundant for the relaxed value)
If , the linear programs and have the same optimal value.
Proof
(Clip every coordinate above one)
The second program has fewer feasible points, so its value is at least the first. Conversely, given feasible for the first, replace every by . A coverage row containing such an entry still receives at least from that entry alone, and the other rows are unchanged, so the clipped vector is feasible for the second program. Since , clipping cannot increase cost.
This clipping argument does not say all feasible relaxed vectors are bounded by 1, nor does it apply unchanged with negative costs, as the second worked example shows.
A lower bound made of prices
Assign a nonnegative price to each requirement, subject to
The total price of requirements served by any one choice cannot exceed the cost of that choice. These constraints form the dual of the stated LP relaxation; even without solving the dual, any such prices prove a lower bound.
Theorem 27.1.3
(Feasible prices bound every cover)
If satisfies and satisfies the price constraints, then . In particular is a lower bound on the cost of every cover, and a cover whose cost equals is optimal.
Proof
(Weight the rows by prices and the columns by the cover)
Multiply each coverage inequality by and add. Since every coefficient is nonnegative, the price constraints can then be multiplied by and summed:
Every binary cover is also relaxed-feasible, so the same lower bound applies to every integer cover. If a concrete cover has cost exactly , the two inequalities certify its optimality without enumerating other covers.
Proof X-ray
Why feasible prices bound every cover
The chain has two inequalities, and each uses a different sign. The first uses : it multiplies the coverage rows , so its gap is , measuring over-coverage of priced requirements. The second uses : it multiplies the price constraints, so its gap is , measuring slack on selected sets.
Key move: the middle equality is only a change in the order of summation, which turns a statement about rows into one about columns.
What the proof never uses: integrality. That is why the bound holds for the relaxation, and why it cannot by itself close the gap to the integer optimum. Strong LP duality says the best price bound equals the relaxation optimum when the LP is feasible and finite; it does not say that this common value must equal the integer optimum. The counterexample below shows a gap.
Worked example 27.1.4
(A matching cover and price certificate)
Take requirements . The available sets and costs are at cost 2, at cost 2, at cost 2, and at cost 3. Selecting covers all four requirements for cost 4. Set for each requirement. Every two-element set has total price 2, no greater than its listed cost, so the price vector is feasible and totals 4. The cover and prices meet: 4 is both the LP and integer optimum. Notice that are merely one certificate of a best solution; the proof does not require uniqueness.
Worked example 27.1.5
(A negative cost breaks the clipping argument)
Add to the previous data a set with cost , say a location that pays a subsidy. Without upper bounds, the relaxed vector covers every requirement for every and costs , which tends to : the relaxation is unbounded below. With the relaxation is bounded, and costs . The two programs now have different values, so the proposition genuinely needs .
For the integer problem the repair is simple: a set of negative cost is always worth selecting, so fix and solve the covering problem for the remaining requirements with the remaining nonnegative costs.
Counterexample mode
The LP optimum need not be a cover
For three requirements, use all three pairs , , , each at cost 1. Setting every covers every row to level 1 at cost . Prices are dual-feasible and total , proving the relaxed optimum. But a single pair misses one requirement, so an integer cover needs at least two sets; any two work. Its optimum is 2. Rounding each down gives no coverage, while rounding all up gives cost 3. Neither operation automatically returns an optimal integer solution.
Reading a certificate carefully
The two gaps identified in the X-ray give an exact test for equality.
Corollary 27.1.6
(Equal values force tightness)
Let be a cover and feasible prices. Then if and only if every selected set has its price constraint tight, and every requirement with positive price is covered exactly once.
Proof
(Both nonnegative gaps must vanish)
By the proof of the theorem, is the sum of the two gaps and , each a sum of nonnegative terms. The difference is zero exactly when every term is zero: forces , and forces .
The converse needs the feasibility and tightness conditions together; a tight constraint alone does not certify a solution. When a gap remains between a cover and prices, the cover is an upper bound on the integer optimum and the price total is a lower bound; neither bound alone identifies the optimum.
Worked example 27.1.7
(Tightness narrows the search for a cover)
Return to the first example with prices . The price sums are against costs , so are tight and is slack. By the corollary, a cover of cost may use only , and since every price is positive it must cover each requirement exactly once.
Requirement lies only in among the tight sets, and requirement only in , so both must be selected. They already cover and once each, and adding would cover them twice. Hence is the only cover these prices can certify, and it does have cost .
Common mistake
(Replacing at least one by exactly one)
Writing the coverage rows as equalities turns covering into partitioning, which may have no solution at all. For requirements and sets , , covering is feasible at cost , but equalities force both sets in and then cover requirement twice, so no partition exists. Use equalities only when overlap is genuinely forbidden.
Practice
Quick check
(Let and choices , , cost 2, 3, 3. Find an optimal cover, prove it optimal, and compare a feasible price bound.)
Solution · Answer
Sets 1 and 2 cover all requirements for cost 5. Choose prices ; the three pair sums are 2, 3 and 3. Their total is 4, so these prices alone give only 4. Sets 1 and 3 also cost 5, and sets 2 and 3 cost 6. Every cover must select at least two sets; since the two least costs sum to 5, 5 is optimal. The LP optimum is 4, attained by choosing half of each set, so no feasible price certificate can total 5.
Quick check
(With requirements , sets and both cost 1. Is the cover feasible? What happens if all three covering inequalities are replaced by equalities?)
Solution · Answer
Yes: select both sets, for cost 2. Equality would force both variables to 1 to cover requirements 1 and 3, but then requirement 2 receives coverage 2, so the partitioning model is infeasible.
Quick check
(For the triangle counterexample, prove the integer optimum directly, and calculate the gap between it and the LP optimum.)
Solution · Answer
One pair contains only two requirements; any two pairs cover all three. Thus the integer optimum is 2. The proven LP optimum is , so the additive gap is and the integer-to-LP ratio is .
Quick check
(A requirement has price , but a proposed cover covers it twice. Can these two feasible objects have equal objective value? Explain.)
Solution · Answer
No. Its contribution to is strictly positive, so the cover cost exceeds the price total by at least that positive gap. Feasibility and nonnegativity prevent other terms from canceling it.