HLPL / VerTeX Modelling Language Documentation

← lessons

Set cover — minimum cost

Sets are not all equal.

Chapter: XII — Set covering · lesson id set-cover-weighted · practice lesson

---

In practice each set has a cost — opening a warehouse, running a sensor, buying coverage. Same coverage matrix, but now minimise the total cost of the chosen sets.

Costs: S₁ = 3, S₂ = 2, S₃ = 5, S₄ = 4. Element 5 still forces S₃ (cost 5). For the rest we compare: cheapest add-on covering both 1 and 2 is S₁ alone (cost 3). Total: 8.

Predict before running

Set costs are S₁=3, S₂=2, S₃=5, S₄=4, and element 5 still lives only in S₃. What is the minimum-cost cover?

• 8 — pick S₃ (forced) plus S₁
• 7 — pick S₃ plus S₂ (cheaper than S₁)
• 5 — pick the two cheapest sets, S₂ and S₁

Starter code

model set_cover
bin y1
bin y2
bin y3
bin y4
constr y1 + y4 >= 1
constr y1 + y2 >= 1
constr y2 + y3 >= 1
constr y3 + y4 >= 1
constr y3 >= 1
min 3*y1 + 2*y2 + 5*y3 + 4*y4
end

import elytica
def main():
  elytica.init_model("set_cover")
  elytica.run_model("set_cover")
  for i in [1,2,3,4]:
    print("y"+str(i), "=", elytica.get_variable_value("set_cover", "y"+str(i)))
  print("obj =", elytica.get_best_primal_bound("set_cover"))
  return 0

Hint

S₃ is still forced (cost 5). Cheapest way to cover {1, 2}: S₁ alone, cost 3. Total = 8.

What counts as correct

• no-error — Model solves
• numeric-match — Minimum-cost cover is 8
• code-contains — Reads the objective from the solver (no hardcoding)

Mastery variant

Same sets as the basic variant, now with prices. Pick the cheapest cover.

model set_cover_v
# S1 = {1,2,3}, S2 = {3,4}, S3 = {4,5}, S4 = {1,5}
bin y1
bin y2
bin y3
bin y4
constr y1 + y4 >= 1
constr y1 >= 1
constr y1 + y2 >= 1
constr y2 + y3 >= 1
constr y3 + y4 >= 1
min 4*y1 + 6*y2 + 3*y3 + 5*y4
end

import elytica
def main():
  elytica.init_model("set_cover_v")
  elytica.run_model("set_cover_v")
  for i in [1,2,3,4]:
    print("y"+str(i), "=", elytica.get_variable_value("set_cover_v", "y"+str(i)))
  print("obj =", elytica.get_best_primal_bound("set_cover_v"))
  return 0

Read this through MCP: read with path: "lessons/set-cover-weighted", or resource hlpl://lessons/set-cover-weighted.