Max Clique API Reference

Data

Data model for Max Clique use case.

`MaxCliqueData`

Bases: UcData

Data for the Max Clique use case.

Finds the largest complete subgraph (clique) in a graph.

Attributes:

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

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

Plot the Max Clique 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]) -> MaxCliqueData` `staticmethod`

Create MaxCliqueData 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
`MaxCliqueData`	The Max Clique data instance.

Raises:

Type	Description
`ValueError`	If the node_names length doesn't match the matrix, or if node_names contains duplicates.

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

Generate a random Max Clique 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
`MaxCliqueData`	A randomly generated data instance.

Examples:

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

Formulation

Formulation for Max Clique use case.

`MaxCliqueFormulation`

Bases: UcFormulation[MaxCliqueData, MaxCliqueSolution]

Constraint-based formulation for Max Clique.

Mathematical Formulation

Decision Variables:
    x_i in {0, 1} -- 1 if node i is in the clique, 0 otherwise.

Objective:
    maximize sum_i x_i

Constraints:
    For each non-edge (i, j): x_i + x_j <= 1

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

Format the formulation as a string.

Parameters:

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

Returns:

Type	Description
`str`	Formatted description of the formulation.

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

Formulate the Max Clique problem as a constraint-based model.

Parameters:

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

Returns:

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

`interpret(solution: Solution, data: MaxCliqueData) -> MaxCliqueSolution` `staticmethod`

Extract a Max Clique solution from the solver result.

Parameters:

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

Returns:

Type	Description
`MaxCliqueSolution`	Structured solution with clique nodes and validity.

Raises:

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

Solution

Solution model for Max Clique use case.

`MaxCliqueSolution`

Bases: UcSolution

Solution for the Max Clique use case.

Attributes:

Name	Type	Description
`name`	`Literal['max_clique']`	Identifier.
`clique_nodes`	`list[int \| str]`	Nodes in the clique.
`clique_size`	`int`	Size of the clique.
`is_valid`	`bool`	Whether all pairs in clique are adjacent.

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

Plot the Max Clique solution on the problem graph.

Clique nodes are highlighted in green; other nodes are grey.

Parameters:

Name	Type	Description	Default
`data`	`MaxCliqueData \| 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 Max Clique use case.

`MaxCliqueInstance`

Bases: UcInstance[MaxCliqueData, MaxCliqueFormulation, MaxCliqueSolution]

Instance combining data and formulation for Max Clique.

Collection

Collection of Max Clique instances.

`MaxCliqueCollection`

Bases: UcInstanceCollection[MaxCliqueInstance]

Collection of Max Clique 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) -> MaxCliqueCollection` `classmethod`

Generate random Max Clique 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
`MaxCliqueCollection`	Collection containing generated instances.

Examples:

>>> collection = MaxCliqueCollection.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.

Max Clique API Reference

Data

MaxCliqueData

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

to_string() -> str

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

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

Formulation

MaxCliqueFormulation

to_string(data: MaxCliqueData) -> str staticmethod

formulate(data: MaxCliqueData) -> Model staticmethod

interpret(solution: Solution, data: MaxCliqueData) -> MaxCliqueSolution staticmethod

Solution

MaxCliqueSolution

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

to_string() -> str

Instance

MaxCliqueInstance

Collection

MaxCliqueCollection

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

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

`MaxCliqueData`

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

`to_string() -> str`

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

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

`MaxCliqueFormulation`

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

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

`interpret(solution: Solution, data: MaxCliqueData) -> MaxCliqueSolution` `staticmethod`

`MaxCliqueSolution`

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

`to_string() -> str`

`MaxCliqueInstance`

`MaxCliqueCollection`

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

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