Exact Cover API Reference

Data

Data model for ExactCover use case.

`ExactCoverData`

Bases: UcData

Data for the Exact Cover Problem.

Given a universe of elements and a collection of subsets, the Exact Cover problem asks whether there exists a sub-collection of subsets such that every element is contained in exactly one subset.

Attributes:

Name	Type	Description
`name`	`Literal['exact_cover']`	Identifier for this data type.
`subset_matrix`	`NumPyArray`	A matrix where each row represents a subset and each column an element. `subset_matrix[i][j] = 1` if subset i contains element j, 0 otherwise.
`n_elements`	`int`	Number of elements in the universe.

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

Plot the subset matrix as a binary heatmap.

Parameters:

Name	Type	Description	Default
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`Axes`	The axes with the plot.

`to_string() -> str`

Return a string describing the data.

Returns:

Type	Description
`str`	String representation of the data.

`from_matrix(subset_matrix: list[list[int]] | NDArray[np.int_]) -> ExactCoverData` `staticmethod`

Create an ExactCoverData instance from a subset matrix.

Parameters:

Name	Type	Description	Default
`subset_matrix`	`list[list[int]] \| NDArray[int_]`	A matrix where each row is a subset and each column an element. `subset_matrix[i][j] = 1` if subset i contains element j.	required

Returns:

Type	Description
`ExactCoverData`	An ExactCoverData instance with the given matrix.

Examples:

>>> data = ExactCoverData.from_matrix([[1, 1, 0], [0, 1, 1]])

`from_subsets(subsets: list[list[int | str]], elements: list[int | str] | None = None) -> ExactCoverData` `staticmethod`

Create an ExactCoverData instance from element and subset lists.

Parameters:

Name	Type	Description	Default
`subsets`	`list[list[int \| str]]`	List of subsets, where each subset is a list of elements.	required
`elements`	`list[int \| str] \| None`	List of all elements in the universe. If `None`, inferred as `list(range(n))` where n is the largest integer element + 1.	`None`

Returns:

Type	Description
`ExactCoverData`	An ExactCoverData instance with the generated subset matrix.

Examples:

>>> data = ExactCoverData.from_subsets(
...     subsets=[[0, 1], [2, 3], [1, 2]],
... )

`generate_random(n_elements: int = 5, n_subsets: int = 8, density: float = 0.4, seed: int | None = None) -> ExactCoverData` `staticmethod`

Generate a random exact cover instance.

Parameters:

Name	Type	Description	Default
`n_elements`	`int`	Number of elements in the universe, by default 5.	`5`
`n_subsets`	`int`	Number of subsets, by default 8.	`8`
`density`	`float`	Probability that an element is included in a subset, by default 0.4.	`0.4`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`ExactCoverData`	A randomly generated exact cover instance.

Formulation

Formulation for ExactCover use case.

`ExactCoverFormulation`

Bases: UcFormulation[ExactCoverData, ExactCoverSolution]

Constraint-based formulation for the Exact Cover Problem.

Mathematical Formulation

Decision Variables:
    x_s in {0,1} for each subset s: 1 if subset s is selected

Objective:
    minimize sum_s x_s (minimize number of subsets used)

Constraints:
    For each element e:
        sum_{s containing e} x_s == 1
    (each element must be covered exactly once)

`to_string(data: ExactCoverData) -> str` `staticmethod`

Return a string describing the formulation.

Parameters:

Name	Type	Description	Default
`data`	`ExactCoverData`	The problem data.	required

Returns:

Type	Description
`str`	String representation of the formulation.

`formulate(data: ExactCoverData) -> Model` `staticmethod`

Formulate the Exact Cover Problem using constraint-based approach.

Parameters:

Name	Type	Description	Default
`data`	`ExactCoverData`	The Exact Cover instance data.	required

Returns:

Type	Description
`Model`	A LunaModel ready to be solved.

Raises:

Type	Description
`EmptyDataError`	If the subset matrix is empty or has zero size.
`InvalidProblemStructureError`	If any element is not covered by any subset (infeasible problem).

`interpret(solution: Solution, data: ExactCoverData) -> ExactCoverSolution` `staticmethod`

Extract solution from quantum result.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The quantum solution.	required
`data`	`ExactCoverData`	The problem data.	required

Returns:

Type	Description
`ExactCoverSolution`	Structured solution with metrics.

Solution

Solution model for ExactCover use case.

`ExactCoverSolution`

Bases: UcSolution

Solution for the Exact Cover Problem.

Attributes:

Name	Type	Description
`name`	`Literal['exact_cover']`	Identifier for this solution type.
`selected_subsets`	`list[int]`	Indices of selected subsets forming the exact cover.
`n_subsets_used`	`int`	Number of subsets used in the solution.
`is_valid`	`bool`	Whether each element is covered exactly once.

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

Plot the exact cover solution.

Parameters:

Name	Type	Description	Default
`data`	`ExactCoverData \| None`	Problem data for context.	`None`
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`Axes`	The axes with the plot.

`to_string() -> str`

Return a string describing the solution.

Returns:

Type	Description
`str`	String representation of the solution.

Instance

Instance model for ExactCover use case.

`ExactCoverInstance`

Bases: UcInstance[ExactCoverData, ExactCoverFormulation, ExactCoverSolution]

Instance combining data and formulation for ExactCover.

Collection

Collection of ExactCover instances.

`ExactCoverCollection`

Bases: UcInstanceCollection[ExactCoverInstance]

Collection of Exact Cover instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.

`from_random(min_num_elements: int | None = None, max_num_elements: int | None = None, num_instances: int = 1, *, sizes: Sequence[int] | None = None, density: float = 0.4, subset_ratio: float = 1.6, seed: int | None = None) -> ExactCoverCollection` `classmethod`

Generate random exact cover instances.

Parameters:

Name	Type	Description	Default
`min_num_elements`	`int \| None`	Minimum number of elements per instance.	`None`
`max_num_elements`	`int \| None`	Maximum number of elements per instance.	`None`
`num_instances`	`int`	Number of instances per size, by default 1.	`1`
`density`	`float`	Probability that an element is included in a subset, by default 0.4.	`0.4`
`subset_ratio`	`float`	Ratio of subsets to elements, by default 1.6.	`1.6`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`
`sizes`	`Sequence[int] \| None`	Explicit sizes to generate, e.g. `[10, 50, 100]`, instead of a range. Mutually exclusive with `min_num_elements`/`max_num_elements`, by default None.	`None`

Returns:

Type	Description
`ExactCoverCollection`	Collection containing generated instances.

`filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]`

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

Name	Type	Description	Default
`max_runtime`	`float`	SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.	`3600`
`quiet`	`bool`	Suppress the SCIP solver output.	`True`

Returns:

Type	Description
`list[bool]`	Feasibility mask over the instances as they were before filtering, in that order: `True` where the instance was kept, `False` where it was removed.

Raises:

Type	Description
`ValueError`	If `max_runtime` is not positive.

Exact Cover API Reference

Data

ExactCoverData

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

to_string() -> str

from_matrix(subset_matrix: list[list[int]] | NDArray[np.int_]) -> ExactCoverData staticmethod

from_subsets(subsets: list[list[int | str]], elements: list[int | str] | None = None) -> ExactCoverData staticmethod

generate_random(n_elements: int = 5, n_subsets: int = 8, density: float = 0.4, seed: int | None = None) -> ExactCoverData staticmethod

Formulation

ExactCoverFormulation

to_string(data: ExactCoverData) -> str staticmethod

formulate(data: ExactCoverData) -> Model staticmethod

interpret(solution: Solution, data: ExactCoverData) -> ExactCoverSolution staticmethod

Solution

ExactCoverSolution

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

to_string() -> str

Instance

ExactCoverInstance

Collection

ExactCoverCollection

from_random(min_num_elements: int | None = None, max_num_elements: int | None = None, num_instances: int = 1, *, sizes: Sequence[int] | None = None, density: float = 0.4, subset_ratio: float = 1.6, seed: int | None = None) -> ExactCoverCollection classmethod

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

`ExactCoverData`

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

`to_string() -> str`

`from_matrix(subset_matrix: list[list[int]] | NDArray[np.int_]) -> ExactCoverData` `staticmethod`

`from_subsets(subsets: list[list[int | str]], elements: list[int | str] | None = None) -> ExactCoverData` `staticmethod`

`generate_random(n_elements: int = 5, n_subsets: int = 8, density: float = 0.4, seed: int | None = None) -> ExactCoverData` `staticmethod`

`ExactCoverFormulation`

`to_string(data: ExactCoverData) -> str` `staticmethod`

`formulate(data: ExactCoverData) -> Model` `staticmethod`

`interpret(solution: Solution, data: ExactCoverData) -> ExactCoverSolution` `staticmethod`

`ExactCoverSolution`

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

`to_string() -> str`

`ExactCoverInstance`

`ExactCoverCollection`

`from_random(min_num_elements: int | None = None, max_num_elements: int | None = None, num_instances: int = 1, *, sizes: Sequence[int] | None = None, density: float = 0.4, subset_ratio: float = 1.6, seed: int | None = None) -> ExactCoverCollection` `classmethod`

`filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]`