Skip to content

Set Cover API Reference

Data

Data model for SetCover use case.

SetCoverData

Bases: UcData

Data for the Set Cover Problem.

Given a set S and a list of subsets of S, so that each element of S is contained in at least one of the subsets, the Set Cover problem tries to find the smallest possible family C of these subsets so that all elements of S are contained in at least one subset of C.

Attributes:

  • name (Literal['set_cover']) –

    Identifier for this data type.

  • subset_matrix (list[list[float]]) –

    A matrix containing all subsets. Each row represents a subset, and each column represents an element. subset_matrix[i][j] = 1 if subset i contains element j, 0 otherwise. Example: for the set {1, 2, 3} and the subsets {1, 2}, {2, 3}, and {3}: [[1, 1, 0], [0, 1, 1], [0, 0, 1]]

Examples:

Create a simple set cover instance:

>>> data = SetCoverData(subset_matrix=[[1, 1, 0], [0, 1, 1], [0, 0, 1]])

Or use the helper method:

>>> data = SetCoverData.from_subset_elements(elements=[1, 2, 3], subsets=[[1, 2], [2, 3], [3]])

plot(*, ax: Axes | None = None) -> Axes

Plot the subset matrix as a binary heatmap.

Each row represents a subset and each column an element. Filled cells (blue) indicate that the element belongs to the subset.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Print the data.

Returns:

  • str –

    String representation of the data.

from_matrix(subset_matrix: list[list[float]] | NDArray[np.float32]) -> SetCoverData staticmethod

Create a SetCoverData instance from a subset matrix.

Parameters:

  • subset_matrix (list[list[float]] | NDArray[float32]) –

    A matrix where each row is a subset and each column an element. subset_matrix[i][j] = 1 if subset i contains element j.

Returns:

  • SetCoverData –

    A SetCoverData instance with the given matrix.

from_subset_elements(elements: list[int | str], subsets: list[list[int | str]]) -> SetCoverData staticmethod

Generate SetCoverData from element and subset lists.

Parameters:

  • elements (list[int | str]) –

    List of all elements in the universe set.

  • subsets (list[list[int | str]]) –

    List of subsets, where each subset is a list of elements.

Returns:

  • SetCoverData –

    The SetCoverData instance with the generated subset matrix.

Examples:

>>> data = SetCoverData.from_subset_elements(elements=[1, 2, 3], subsets=[[1, 2], [2, 3], [3]])

generate_random(n_elements: int = 10, n_subsets: int = 15, coverage_prob: float = 0.3, seed: int | None = None) -> SetCoverData staticmethod

Generate a random set cover instance.

Parameters:

  • n_elements (int, default: 10 ) –

    Number of elements in the universe set, by default 10.

  • n_subsets (int, default: 15 ) –

    Number of subsets, by default 15.

  • coverage_prob (float, default: 0.3 ) –

    Probability that an element is included in a subset, by default 0.3.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> data = SetCoverData.generate_random(n_elements=10, n_subsets=15, coverage_prob=0.3, seed=42)

Formulation

Formulation for SetCover use case.

SetCoverFormulation

Bases: UcFormulation[SetCoverData, SetCoverSolution]

Constraint-based formulation for Set Cover Problem.

This formulation uses Luna Model's constraint system rather than manual QUBO penalty terms (no A, B parameters).

Mathematical Formulation

Given: - S: universe set with n elements - F: family of m subsets of S

Decision Variables: x_i ∈ {0,1} for each subset i ∈ {0, ..., m-1} x_i = 1 if subset i is selected, 0 otherwise

Objective: minimize Σ_i x_i (minimize the number of subsets)

Constraints: For each element e ∈ S: Σ_{i: e ∈ subset_i} x_i ≥ 1 (each element must be covered by at least one selected subset)

References
  • Wikipedia: https://en.wikipedia.org/wiki/Set_cover_problem
  • QUBO Transformation: https://arxiv.org/pdf/1302.5843.pdf

to_string(data: SetCoverData) -> str staticmethod

Print the formulation.

Parameters:

Returns:

  • str –

    String representation of the formulation.

formulate(data: SetCoverData) -> Model staticmethod

Formulate the Set Cover Problem using constraint-based approach.

Creates a constraint-based formulation using binary decision variables for subset selection and coverage constraints for each element.

Parameters:

  • data (SetCoverData) –

    The Set Cover instance data containing the subset matrix.

Returns:

  • Model –

    A Luna Model ready to be solved.

Raises:

interpret(solution: Solution, data: SetCoverData) -> SetCoverSolution staticmethod

Extract solution from quantum result.

Extracts the selected subsets from the quantum solution and computes solution metrics like coverage statistics and validity.

Parameters:

  • solution (Solution) –

    The quantum solution containing variable assignments.

  • data (SetCoverData) –

    The original Set Cover instance data.

Returns:

  • SetCoverSolution –

    A structured solution object with selected subsets and metrics.

Raises:

Solution

Solution model for SetCover use case.

SetCoverSolution

Bases: UcSolution

Solution for the Set Cover Problem.

Attributes:

  • name (Literal['set_cover']) –

    Identifier for this solution type.

  • selected_subsets (NumPyArray) –

    Indices of subsets that are part of the set cover.

  • n_subsets_used (int) –

    Number of subsets used in the cover (length of selected_subsets).

  • elements_covered (NumPyArray) –

    Count of how many times each element is covered (should be >= 1 for valid solutions).

  • is_valid (bool) –

    Whether the solution is valid (all elements are covered at least once).

plot(data: SetCoverData | None = None, *, ax: Axes | None = None) -> Axes

Plot the set cover solution.

When data is provided the subset matrix is shown as a heatmap with selected rows highlighted in green and unselected rows greyed out. Without data a bar chart of per-element coverage counts is drawn instead.

Parameters:

  • data (SetCoverData | None, default: None ) –

    Problem data. When provided, the subset matrix heatmap is drawn with selection highlights.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Print the solution.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for SetCover use case.

SetCoverInstance

Bases: UcInstance[SetCoverData, SetCoverFormulation, SetCoverSolution]

Instance combining data and formulation for SetCover.

Collection

Collection of SetCover instances.

SetCoverCollection

Bases: UcInstanceCollection[SetCoverInstance]

Collection of Set Cover Problem instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation, including sparse, dense, and redundant coverage patterns.

from_random(min_num_elements: int, max_num_elements: int, num_instances: int = 1, *, subset_ratio: float = 1.5, coverage_prob: float = 0.3, seed: int | None = None) -> SetCoverCollection classmethod

Generate random set cover instances.

In random instances, each element has a fixed probability of being included in each subset. The number of subsets is proportional to the number of elements.

Parameters:

  • min_num_elements (int) –

    Minimum number of elements per instance.

  • max_num_elements (int) –

    Maximum number of elements per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • subset_ratio (float, default: 1.5 ) –

    Ratio of subsets to elements, by default 1.5. E.g., 1.5 means n_subsets = 1.5 * n_elements.

  • coverage_prob (float, default: 0.3 ) –

    Probability that an element is included in a subset, by default 0.3.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = SetCoverCollection.from_random(
...     min_num_elements=5,
...     max_num_elements=10,
...     num_instances=3,
...     coverage_prob=0.4,
...     seed=42,
... )

from_sparse(min_num_elements: int, max_num_elements: int, num_instances: int = 1, *, subset_ratio: float = 2.0, coverage_prob: float = 0.15, seed: int | None = None) -> SetCoverCollection classmethod

Generate sparse set cover instances.

Sparse instances have low coverage probability, meaning each subset contains only a few elements. This creates instances where more subsets are typically needed to cover all elements.

Parameters:

  • min_num_elements (int) –

    Minimum number of elements per instance.

  • max_num_elements (int) –

    Maximum number of elements per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • subset_ratio (float, default: 2.0 ) –

    Ratio of subsets to elements, by default 2.0.

  • coverage_prob (float, default: 0.15 ) –

    Low probability for sparse coverage, by default 0.15.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = SetCoverCollection.from_sparse(
...     min_num_elements=10,
...     max_num_elements=20,
...     num_instances=5,
...     seed=42,
... )

from_dense(min_num_elements: int, max_num_elements: int, num_instances: int = 1, *, subset_ratio: float = 1.2, coverage_prob: float = 0.5, seed: int | None = None) -> SetCoverCollection classmethod

Generate dense set cover instances.

Dense instances have high coverage probability, meaning each subset contains many elements. This creates instances with high redundancy where fewer subsets are needed to cover all elements.

Parameters:

  • min_num_elements (int) –

    Minimum number of elements per instance.

  • max_num_elements (int) –

    Maximum number of elements per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • subset_ratio (float, default: 1.2 ) –

    Ratio of subsets to elements, by default 1.2.

  • coverage_prob (float, default: 0.5 ) –

    High probability for dense coverage, by default 0.5.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = SetCoverCollection.from_dense(
...     min_num_elements=8,
...     max_num_elements=15,
...     coverage_prob=0.6,
...     seed=42,
... )

from_uniform(min_num_elements: int, max_num_elements: int, num_instances: int = 1, *, elements_per_subset: int = 3, subsets_per_element: int = 3, seed: int | None = None) -> SetCoverCollection classmethod

Generate uniform set cover instances.

Uniform instances aim to have approximately the same number of elements per subset and the same number of subsets covering each element.

Parameters:

  • min_num_elements (int) –

    Minimum number of elements per instance.

  • max_num_elements (int) –

    Maximum number of elements per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • elements_per_subset (int, default: 3 ) –

    Target number of elements per subset, by default 3.

  • subsets_per_element (int, default: 3 ) –

    Target number of subsets covering each element, by default 3.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = SetCoverCollection.from_uniform(
...     min_num_elements=9,
...     max_num_elements=15,
...     elements_per_subset=4,
...     seed=42,
... )

from_redundant(min_num_elements: int, max_num_elements: int, num_instances: int = 1, *, subset_ratio: float = 2.5, coverage_prob: float = 0.4, seed: int | None = None) -> SetCoverCollection classmethod

Generate highly redundant set cover instances.

Redundant instances have many subsets relative to elements and high coverage probability, creating instances with many overlapping subsets. This tests the solver's ability to find minimal covers when many solutions exist.

Parameters:

  • min_num_elements (int) –

    Minimum number of elements per instance.

  • max_num_elements (int) –

    Maximum number of elements per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • subset_ratio (float, default: 2.5 ) –

    High ratio of subsets to elements, by default 2.5.

  • coverage_prob (float, default: 0.4 ) –

    Coverage probability, by default 0.4.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = SetCoverCollection.from_redundant(
...     min_num_elements=5,
...     max_num_elements=12,
...     subset_ratio=3.0,
...     seed=42,
... )