HLPL / VerTeX Modelling Language Documentation

← lessons

Set cover — minimum number of sets

Cover every element with as few sets as possible.

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

---

Five elements {1, 2, 3, 4, 5}. Four candidate sets:

S₁ = {1, 2} S₂ = {2, 3} S₃ = {3, 4, 5} S₄ = {1, 4}

Pick the minimum number of sets that together cover every element. Each set is a binary y_s.

One constraint per element: at least one chosen set must include it. Element 5 lives only in S₃, so S₃ is forced. Then we need any single set covering both 1 and 2 — S₁ does it. Optimum: 2 sets {S₁, S₃}.

Predict before running

Element 5 appears only in S₃. What does this force?

• S₃ must be picked
• S₃ should be avoided (it has the fewest elements)
• Doesn't affect anything. The solver decides

Starter code

model set_cover
bin y1
bin y2
bin y3
bin y4
constr y1 + y4 >= 1     # element 1
constr y1 + y2 >= 1     # element 2
constr y2 + y3 >= 1     # element 3
constr y3 + y4 >= 1     # element 4
constr y3 >= 1          # element 5
min y1 + y2 + y3 + 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

Element 5 is only in S₃ → S₃ must be picked. Then S₁ covers the rest.

What counts as correct

• no-error — Model solves
• numeric-match — Minimum cover uses 2 sets
• numeric-match — S₃ is forced (element 5)
• code-contains — Reads the objective from the solver (no hardcoding)
• code-contains — Reads variable values from the solver (no hardcoding)

Mastery variant

Different sets and elements. Still find the smallest 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     # element 1
constr y1 >= 1          # element 2 (only in S1)
constr y1 + y2 >= 1     # element 3
constr y2 + y3 >= 1     # element 4
constr y3 + y4 >= 1     # element 5
min y1 + y2 + y3 + 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-basic", or resource hlpl://lessons/set-cover-basic.