Minimum Vertex Cover API Reference

Data

Data model for Minimum Vertex Cover use case.

`MinimumVertexCoverData`

Bases: UcData

Data for the Minimum Vertex Cover use case.

Finds the smallest set of vertices such that every edge has at least one endpoint in the set.

Attributes:

Name	Type	Description
`name`	`Literal['minimum_vertex_cover']`	Identifier.
`adjacency_matrix`	`BinAdjMatrix`	Symmetric binary adjacency matrix.
`node_names`	`list[int \| str]`	Node identifiers.

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

Plot the Minimum Vertex Cover graph instance.

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`

Format the data as a human-readable string.

Returns:

Type	Description
`str`	String representation of the data.

`from_adjacency_matrix(adjacency_matrix: NDArray[np.float64], node_names: list[int | str]) -> MinimumVertexCoverData` `staticmethod`

Create MinimumVertexCoverData from an adjacency matrix.

Parameters:

Name	Type	Description	Default
`adjacency_matrix`	`ndarray`	Symmetric binary adjacency matrix.	required
`node_names`	`list[int \| str]`	Node identifiers.	required

Returns:

Type	Description
`MinimumVertexCoverData`	The Minimum Vertex Cover data instance.

`generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> MinimumVertexCoverData` `staticmethod`

Generate a random Minimum Vertex Cover instance.

Parameters:

Name	Type	Description	Default
`n_nodes`	`int`	Number of nodes in the graph, by default 5.	`5`
`edge_prob`	`float`	Probability of an edge between any two nodes, by default 0.5.	`0.5`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`MinimumVertexCoverData`	A randomly generated data instance.

Examples:

>>> data = MinimumVertexCoverData.generate_random(n_nodes=5, seed=42)

Formulation

Formulation for Minimum Vertex Cover use case.

`MinimumVertexCoverFormulation`

Bases: UcFormulation[MinimumVertexCoverData, MinimumVertexCoverSolution]

Constraint-based formulation for Minimum Vertex Cover.

Mathematical Formulation

Decision Variables:
    x_i in {0, 1} -- node i is in the cover

Objective:
    minimize sum_i x_i

Constraints:
    For each edge (i, j): x_i + x_j >= 1

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

Format the formulation as a string.

Parameters:

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

Returns:

Type	Description
`str`	Formatted description of the formulation.

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

Formulate the Minimum Vertex Cover problem.

Parameters:

Name	Type	Description	Default
`data`	`MinimumVertexCoverData`	The problem data containing the graph structure.	required

Returns:

Type	Description
`Model`	The optimization model.

`interpret(solution: Solution, data: MinimumVertexCoverData) -> MinimumVertexCoverSolution` `staticmethod`

Extract a structured solution from the solver result.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The solver solution.	required
`data`	`MinimumVertexCoverData`	The problem data.	required

Returns:

Type	Description
`MinimumVertexCoverSolution`	Structured solution with cover nodes and validity.

Raises:

Type	Description
`NoSolutionFoundError`	If no feasible solution was found.

Solution

Solution model for Minimum Vertex Cover use case.

`MinimumVertexCoverSolution`

Bases: UcSolution

Solution for Minimum Vertex Cover.

Attributes:

Name	Type	Description
`name`	`Literal['minimum_vertex_cover']`	Identifier.
`cover_nodes`	`list[int \| str]`	Nodes in the cover.
`cover_size`	`int`	Number of nodes in the cover.
`is_valid`	`bool`	Every edge has at least one endpoint in cover.

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

Plot the Minimum Vertex Cover solution on the problem graph.

Nodes in the cover are highlighted in a different color.

Parameters:

Name	Type	Description	Default
`data`	`MinimumVertexCoverData \| None`	Problem data used to reconstruct the graph. Required -- a `ValueError` is raised when `None`.	`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.

Raises:

Type	Description
`ValueError`	If data is `None`.

`to_string() -> str`

Format the solution as a human-readable string.

Returns:

Type	Description
`str`	String representation of the solution.

Instance

Instance model for Minimum Vertex Cover use case.

`MinimumVertexCoverInstance`

Bases: UcInstance[MinimumVertexCoverData, MinimumVertexCoverFormulation, MinimumVertexCoverSolution]

Instance combining data and formulation for Minimum Vertex Cover.

Collection

Collection of Minimum Vertex Cover instances.

`MinimumVertexCoverCollection`

Bases: UcInstanceCollection[MinimumVertexCoverInstance]

Collection of Minimum Vertex Cover instances.

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

`from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> MinimumVertexCoverCollection` `classmethod`

Generate random Minimum Vertex Cover instances.

Parameters:

Name	Type	Description	Default
`min_nodes`	`int \| None`	Minimum number of nodes per instance.	`None`
`max_nodes`	`int \| None`	Maximum number of nodes per instance.	`None`
`edge_prob`	`float`	Probability of an edge between any two nodes, by default 0.5.	`0.5`
`num_instances`	`int`	Number of instances per node count, by default 1.	`1`
`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_nodes`/`max_nodes`, by default None.	`None`

Returns:

Type	Description
`MinimumVertexCoverCollection`	Collection containing generated instances.

Examples:

>>> collection = MinimumVertexCoverCollection.from_random(
...     min_nodes=4,
...     max_nodes=6,
...     num_instances=2,
...     seed=42,
... )

`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.

Minimum Vertex Cover API Reference

Data

MinimumVertexCoverData

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

to_string() -> str

from_adjacency_matrix(adjacency_matrix: NDArray[np.float64], node_names: list[int | str]) -> MinimumVertexCoverData staticmethod

generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> MinimumVertexCoverData staticmethod

Formulation

MinimumVertexCoverFormulation

to_string(data: MinimumVertexCoverData) -> str staticmethod

formulate(data: MinimumVertexCoverData) -> Model staticmethod

interpret(solution: Solution, data: MinimumVertexCoverData) -> MinimumVertexCoverSolution staticmethod

Solution

MinimumVertexCoverSolution

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

to_string() -> str

Instance

MinimumVertexCoverInstance

Collection

MinimumVertexCoverCollection

from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> MinimumVertexCoverCollection classmethod

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

`MinimumVertexCoverData`

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

`to_string() -> str`

`from_adjacency_matrix(adjacency_matrix: NDArray[np.float64], node_names: list[int | str]) -> MinimumVertexCoverData` `staticmethod`

`generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> MinimumVertexCoverData` `staticmethod`

`MinimumVertexCoverFormulation`

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

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

`interpret(solution: Solution, data: MinimumVertexCoverData) -> MinimumVertexCoverSolution` `staticmethod`

`MinimumVertexCoverSolution`

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

`to_string() -> str`

`MinimumVertexCoverInstance`

`MinimumVertexCoverCollection`

`from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> MinimumVertexCoverCollection` `classmethod`

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