Skip to content

Set Cover Example

Download Notebook

The Set Cover Problem (SCP) asks for the smallest collection of subsets that covers every element of a universe set. It is NP-hard and arises in facility placement, crew scheduling, and resource allocation.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.set_cover import (
    SetCoverCollection,
    SetCoverData,
    SetCoverFormulation,
    SetCoverInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define a universe of 5 elements and 4 subsets using element lists.

data = SetCoverData.from_subset_elements(
    elements=[1, 2, 3, 4, 5],
    subsets=[
        [1, 2],  # Subset 0
        [2, 3, 4],  # Subset 1
        [4, 5],  # Subset 2
        [1, 5],  # Subset 3
    ],
)
print(data.to_string())

Set Cover Problem:
  Number of elements: 5
  Number of subsets: 4
  Subset matrix shape: (4, 5)
  Subset 0: elements [0, 1]
  Subset 1: elements [1, 2, 3]
  Subset 2: elements [3, 4]
  Subset 3: elements [0, 4]

Plot Data

Visualize the subset matrix as a binary heatmap.

data.plot()


<Axes: title={'center': 'Set Cover — Subset Matrix'}, xlabel='Element j', ylabel='Subset i'>
png

Create Formulation

Set up binary decision variables selecting subsets to minimize the number of subsets used while covering all elements.

formulation = SetCoverFormulation()
print(formulation.to_string(data))

Set Cover Formulation:
  Subsets: 4
  Elements: 5

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 3
  x[i] = 1 if subset i is selected
  Total: 4 binary variables

Objective:
  minimize sum_i x[i]  for i = 0, ..., 3

Constraints:
  1. Coverage constraints (5 constraints):
     sum_{i: e in subset_i} x[i] >= 1  for all e = 0, ..., 4

Create Instance

Combine data and formulation into a solvable instance.

instance = SetCoverInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Set Cover Problem:
  Number of elements: 5
  Number of subsets: 4
  Subset matrix shape: (4, 5)
  Subset 0: elements [0, 1]
  Subset 1: elements [1, 2, 3]
  Subset 2: elements [3, 4]
  Subset 3: elements [0, 4]
Formulation:Set Cover Formulation:
  Subsets: 4
  Elements: 5

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 3
  x[i] = 1 if subset i is selected
  Total: 4 binary variables

Objective:
  minimize sum_i x[i]  for i = 0, ..., 3

Constraints:
  1. Coverage constraints (5 constraints):
     sum_{i: e in subset_i} x[i] >= 1  for all e = 0, ..., 4

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')










2026-05-29 11:35:54 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.










Set Cover Solution:
  Number of subsets used: 2
  Selected subsets: [1 3]
  Elements covered: [1 1 1 1 1]
  Valid (all elements covered): True



Plot Solution


Visualize the optimal solution.


uc_solution.plot(data)



<Axes: title={'center': 'Set Cover Solution — 2 subsets'}, xlabel='Element j', ylabel='Subset i'>


png


Collections


Generate a benchmark collection of random instances for batch processing.


collection = SetCoverCollection.from_random(min_num_elements=5, max_num_elements=8, seed=42)
model = collection.instances[0].formulate()
print(model)



Model: set_cover<set_cover>
Minimize
  x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6
Subject To
  cover_element_0: x_0 + x_1 + x_2 + x_4 >= 1
  cover_element_1: x_1 + x_2 + x_3 + x_4 + x_5 + x_6 >= 1
  cover_element_2: x_0 + x_3 + x_5 >= 1
  cover_element_3: x_3 >= 1
  cover_element_4: x_4 >= 1
Binary
  x_0 x_1 x_2 x_3 x_4 x_5 x_6