Minimal Maximal Matching API Reference

Data

Data model for Minimal Maximal Matching use case.

`MinimalMaximalMatchingData`

Bases: UcData

Data for the Minimal Maximal Matching use case.

Finds a maximal matching with the minimum number of edges. A matching is maximal if no more edges can be added without violating the matching property (no shared vertices).

Attributes:

Name	Type	Description
`name`	`Literal['minimal_maximal_matching']`	Identifier for this data type.
`adjacency_matrix`	`NumPyArray`	Symmetric binary adjacency matrix.
`node_names`	`list[int \| str]`	Node identifiers.

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

Plot the 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: np.ndarray, node_names: list[int | str]) -> MinimalMaximalMatchingData` `staticmethod`

Create data from an adjacency matrix.

Parameters:

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

Returns:

Type	Description
`MinimalMaximalMatchingData`	The data instance.

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

Generate a random instance.

Parameters:

Name	Type	Description	Default
`n_nodes`	`int`	Number of nodes, 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
`MinimalMaximalMatchingData`	A randomly generated data instance.

Examples:

>>> data = MinimalMaximalMatchingData.generate_random(n_nodes=10, seed=42)

Formulation

Formulation for Minimal Maximal Matching use case.

`MinimalMaximalMatchingFormulation`

Bases: UcFormulation[MinimalMaximalMatchingData, MinimalMaximalMatchingSolution]

Constraint-based formulation for Minimal Maximal Matching.

Mathematical Formulation

Decision Variables:
    y_e ∈ {0, 1} -- 1 if edge e is in the matching.

Objective:
    minimize Σ_e y_e

Constraints:
    1. Matching: for each node v: Σ_{e incident to v} y_e ≤ 1
    2. Maximal: for each edge (u,v): y_(u,v) + Σ_{e≠(u,v) incident to u} y_e
       + Σ_{e≠(u,v) incident to v} y_e ≥ 1

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

Format the formulation as a string.

Parameters:

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

Returns:

Type	Description
`str`	Formatted description of the formulation.

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

Formulate the Minimal Maximal Matching problem.

Parameters:

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

Returns:

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

`interpret(solution: Solution, data: MinimalMaximalMatchingData) -> MinimalMaximalMatchingSolution` `staticmethod`

Extract a Minimal Maximal Matching solution from the solver result.

Parameters:

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

Returns:

Type	Description
`MinimalMaximalMatchingSolution`	Structured solution with matching edges and validity.

Raises:

Type	Description
`NoSolutionFoundError`	If the solver did not find any solution.

Solution

Solution model for Minimal Maximal Matching use case.

`MinimalMaximalMatchingSolution`

Bases: UcSolution

Solution for the Minimal Maximal Matching use case.

Attributes:

Name	Type	Description
`name`	`Literal['minimal_maximal_matching']`	Identifier.
`matching_edges`	`list[tuple[int \| str, int \| str]]`	Edges in the matching.
`matching_size`	`int`	Number of edges in the matching.
`is_valid`	`bool`	Whether the matching is valid (no shared vertices) and maximal.

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

Plot the solution on the problem graph.

Matching edges are highlighted in green; other edges are grey.

Parameters:

Name	Type	Description	Default
`data`	`MinimalMaximalMatchingData \| None`	Problem data. Required.	`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 Minimal Maximal Matching use case.

`MinimalMaximalMatchingInstance`

Bases: UcInstance[MinimalMaximalMatchingData, MinimalMaximalMatchingFormulation, MinimalMaximalMatchingSolution]

Instance combining data and formulation for Minimal Maximal Matching.

Collection

Collection of Minimal Maximal Matching instances.

`MinimalMaximalMatchingCollection`

Bases: UcInstanceCollection[MinimalMaximalMatchingInstance]

Collection of Minimal Maximal Matching instances.

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) -> MinimalMaximalMatchingCollection` `classmethod`

Generate random Minimal Maximal Matching instances.

Parameters:

Name	Type	Description	Default
`min_nodes`	`int \| None`	Minimum number of nodes.	`None`
`max_nodes`	`int \| None`	Maximum number of nodes.	`None`
`edge_prob`	`float`	Edge probability, by default 0.5.	`0.5`
`num_instances`	`int`	Number of instances per size, 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
`MinimalMaximalMatchingCollection`	Collection containing generated instances.

Examples:

>>> collection = MinimalMaximalMatchingCollection.from_random(
...     min_nodes=5,
...     max_nodes=10,
...     num_instances=3,
...     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.

Minimal Maximal Matching API Reference

Data

MinimalMaximalMatchingData

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

to_string() -> str

from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str]) -> MinimalMaximalMatchingData staticmethod

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

Formulation

MinimalMaximalMatchingFormulation

to_string(data: MinimalMaximalMatchingData) -> str staticmethod

formulate(data: MinimalMaximalMatchingData) -> Model staticmethod

interpret(solution: Solution, data: MinimalMaximalMatchingData) -> MinimalMaximalMatchingSolution staticmethod

Solution

MinimalMaximalMatchingSolution

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

to_string() -> str

Instance

MinimalMaximalMatchingInstance

Collection

MinimalMaximalMatchingCollection

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) -> MinimalMaximalMatchingCollection classmethod

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

`MinimalMaximalMatchingData`

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

`to_string() -> str`

`from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str]) -> MinimalMaximalMatchingData` `staticmethod`

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

`MinimalMaximalMatchingFormulation`

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

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

`interpret(solution: Solution, data: MinimalMaximalMatchingData) -> MinimalMaximalMatchingSolution` `staticmethod`

`MinimalMaximalMatchingSolution`

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

`to_string() -> str`

`MinimalMaximalMatchingInstance`

`MinimalMaximalMatchingCollection`

`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) -> MinimalMaximalMatchingCollection` `classmethod`

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